Two-way string-matching algorithm

Class	String-searching algorithm
Data structure	Anystringwith an ordered alphabet
Worst-caseperformance	O(n)
Best-caseperformance	O(n)
Worst-casespace complexity	⌈log₂m⌉

Incomputer science,thetwo-way string-matching algorithmis astring-searching algorithm,discovered byMaxime CrochemoreandDominique Perrinin 1991.It takes a pattern of sizem,called a “needle”, preprocesses it in linear timeO(m), producing information that can then be used to search for the needle in any “haystack” string, taking only linear time O(n) withnbeing the haystack's length.

The two-way algorithm can be viewed as a combination of the forward-goingKnuth–Morris–Pratt algorithm(KMP) and the backward-runningBoyer–Moore string-search algorithm(BM). Like those two, the 2-way algorithm preprocesses the pattern to find partially repeating periods and computes “shifts” based on them, indicating what offset to “jump” to in the haystack when a given character is encountered.

Unlike BM and KMP, it uses onlyO(logm) additional space to store information about those partial repeats: the search pattern is split into two parts (its critical factorization), represented only by the position of that split. Being a number less thanm,it can be represented in ⌈log₂m⌉ bits. This is sometimes treated as "close enough to O(1) in practice", as the needle's size is limited by the size ofaddressable memory;the overhead is a number that can be stored in a single register, and treating it as O(1) is like treating the size of a loop counter as O(1) rather than log of the number of iterations. The actual matching operation performs at most 2n−mcomparisons.

Breslauer later published two improved variants performing fewer comparisons, at the cost of storing additional data about the preprocessed needle:

• The first one performs at mostn+ ⌊(n−m)/2⌋ comparisons, ⌈(n−m)/2⌉ fewer than the original. It must however store ⌈log_$\varphi$m⌉ additional offsets in the needle, using O(log²m) space.
• The second adapts it to only store a constant number of such offsets, denotedc,but must performn+ ⌊(1⁄2+ ε) * (n−m)⌋ comparisons, with ε =1⁄2(F_c+2− 1)⁻¹= O($\varphi$^−c) going to zero exponentially quickly ascincreases.

The algorithm is considered fairly efficient in practice, being cache-friendly and using several operations that can be implemented in well-optimized subroutines. It is used by theC standard librariesglibc,newlib,andmusl,to implement thememmemandstrstrfamily ofsubstring functions.As with most advanced string-search algorithms, the naïve implementation may be more efficient on small-enough instances;this is especially so if the needle isn't searched in multiple haystacks, which would amortize the preprocessing cost.

Critical factorization

Before we define critical factorization, we should define:

• Factorization:a string is considered factorized when it is split into two parts. Suppose a stringxis split into two parts(u, v),then(u, v)is called a factorization ofx.
• Period:a periodpfor a stringxis defined as a value such that for any integer0 <i≤len(x)−p,x[i] =x[i+p].In other words, "pis a period ofxif two letters ofxat distancepalways coincide ". The minimum period ofxis a positive integer denoted asp(x).
• Arepetitionwin(u, v)is a string such that:
  • wis a suffix ofuoruis a suffix ofw;
  • wis a prefix ofvorvis a prefix ofw;

  In other words,woccurs on both sides of the cut with a possible overflow on either side. Each factorization trivially has at least one repetition, the stringvu.

• Alocal periodis the length of a repetition in(u, v).The smallest local period in(u, v)is denoted asr(u, v).For any factorization,0 <r(u, v)≤len(x).
• Acritical factorizationis a factorization(u, v)ofxsuch thatr(u, v)=p(x).For a needle of lengthmin an ordered alphabet, it can be computed in2mcomparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.

The algorithm

The algorithm starts by critical factorization of the needle as the preprocessing step. This step produces the index (starting point) of the periodic right-half, and the period of this stretch. The suffix computation here follows the authors' formulation. It can alternatively be computed using theDuval's algorithm,which is simpler and still linear time but slower in practice.

Shorthand for inversion.
functioncmp(a, b)
ifa > breturn1
ifa = breturn0
ifa < breturn-1

functionmaxsuf(n, rev)
l ← len(n)
p ← 1currently known period.
k ← 1index for period testing, 0 < k <= p.
j ← 0index for maxsuf testing. greater than maxs.
i ← -1the proposed starting index of maxsuf

whilej + k < l
cmpv ← cmp(n[j + k], n[i + k])
ifrev
cmpv ← -cmpvinvert the comparison
ifcmpv < 0
Suffix (j+k) is smaller. Period is the entire prefix so far.
j ← j + k
k ← 1
p ← j - i
else ifcmpv = 0
They are the same - we should go on.
ifk = p
We are done checking this stretch of p. reset k.
j ← j + p
k ← 1
else
k ← k + 1
else
Suffix is larger. Start over from here.
i ← j
j ← j + 1
p ← 1
k ← 1
return[i, p]

functioncrit_fact(n)
[idx1, per1] ← maxsuf(n, false)
[idx2, per2] ← maxsuf(n, true)
ifidx1 > idx2
return[idx1, per1]
else
return[idx2, per2]

The comparison proceeds by first matching for the right-hand-side, and then for the left-hand-side if it matches. Linear-time skipping is done using the period.

functionmatch(n, h)
nl ← len(n)
hl ← len(h)
[l, p] ← crit_fact(n)
P ← {}set of matches.

Match the suffix.
Use a library function like memcmp, or write your own loop.
ifn[0]... n[l] = n[l+1]... n[l+p]
P ← {}
pos ← 0
s ← 0

TODO. At least put the skip in.