View source for Two-way string-matching algorithm

{{Short description|String-searching algorithm}}
{{Infobox algorithm
|name           = <!-- Defaults to article name -->
|class          = [[String-searching algorithm]]
|image          =
|caption        =
|data           = Any [[String (computer science)|string]] with an ordered alphabet
|time           = O(n)
|best-time      = O(n)
|average-time   =
|space          = ⌈log₂ ''m''⌉
}}

In [[computer science]], the '''two-way string-matching algorithm''' is a [[string-searching algorithm]], discovered by [[Maxime Crochemore]] and [[Dominique Perrin]] in 1991.<ref name=CP91>{{cite journal |last1=Crochemore |first1=Maxime |last2=Perrin |first2=Dominique |title=Two-way string-matching |journal=Journal of the ACM |date=1 July 1991 |volume=38 |issue=3 |pages=650–674 |doi=10.1145/116825.116845 |s2cid=15055316 |url=http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf}}</ref>  It takes a pattern of size ''m'', called a “needle”, preprocesses it in linear time [[Landau notation|O]](''m''), producing information that can then be used to search for the needle in any “haystack” string, taking only linear time O(''n'') with ''n'' being the haystack's length.

The two-way algorithm can be viewed as a combination of the forward-going [[Knuth–Morris–Pratt algorithm]] (KMP) and the backward-running [[Boyer–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 only [[Landau notation|O]](log ''m'') 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 than ''m'', 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 of [[Address space|addressable 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 2''n'' − ''m'' comparisons.<ref name=igm-mlv>{{cite web |title=Two Way algorithm |url=http://www-igm.univ-mlv.fr/~lecroq/string/node26.html}}</ref>

Breslauer later published two improved variants performing fewer comparisons, at the cost of storing additional data about the preprocessed needle:<ref>{{cite journal |last1=Breslauer |first1=Dany |title=Saving comparisons in the Crochemore-Perrin string-matching algorithm |journal=Theoretical Computer Science |date=May 1996 |volume=158 |issue=1–2 |pages=177–192 |doi=10.1016/0304-3975(95)00068-2|doi-access=free}}</ref>
* The first one performs at most ''n'' + ⌊(''n'' − ''m'')/2⌋ comparisons, ⌈(''n'' − ''m'')/2⌉ fewer than the original. It must however store ⌈log<sub>[[Golden ratio|{{nowrap|<math>\varphi</math>}}]]</sub> ''m''⌉ additional offsets in the needle, using O(log<sup>2</sup> ''m'') space.
* The second adapts it to only store a constant number of such offsets, denoted ''c'', but must perform ''n'' + ⌊({{frac|1|2}} + ε) * (''n'' − ''m'')⌋ comparisons, with ε = {{frac|1|2}}([[Fibonacci number|''F'']]<sub>''c''+2</sub> − 1)<sup>−1</sup> = O({{nowrap|<math>\varphi</math>}}<sup>−''c''</sup>) going to zero exponentially quickly as ''c'' increases.

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 the [[C standard libraries]] [[glibc]], [[newlib]], and [[musl]], to implement the ''memmem'' and ''strstr'' family of [[C string handling#Functions|substring functions]].<ref>{{cite web |title=musl/src/string/memmem.c |url=http://git.musl-libc.org/cgit/musl/tree/src/string/memmem.c |access-date=23 November 2019}}</ref><ref>{{cite web |title=newlib/libc/string/memmem.c |url=https://chromium.googlesource.com/native_client/nacl-newlib/+/master/newlib/libc/string/memmem.c |access-date=23 November 2019}}</ref><ref name="str-two-way">{{cite web |title=glibc/string/str-two-way.h |url=https://code.woboq.org/userspace/glibc/string/str-two-way.h.html}}</ref> As with most advanced string-search algorithms, the naïve implementation may be more efficient on small-enough instances;<ref>{{cite web |title=Eric Blake - Re: PATCH] Improve performance of memmem |url=https://sourceware.org/ml/newlib/2018/msg01144.html |website=Newlib mailing list}}</ref> 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:<ref name=CP91/>
* A '''factorization''' is a partition {{math|''(u,v)''}} of a string {{math|''x''}}. For example, <code>("Wiki","pedia")</code> is a factorization of <code>"Wikipedia"</code>.
* A '''period''' of a string {{math|''x''}} is an integer {{math|''p''}} such that all characters {{math|''p''}}-distance apart are equal. More precisely, {{math|1=''x''[''i''] = ''x''[''i'' + ''p'']}} holds for any integer {{math|0 &lt; ''i'' &le; ''len(x)'' − ''p''}}. This definition is allowed to be vacuously true, so that any word of length {{math|''n''}} has a period of {{math|''n''}}. To illustrate, the 8-letter word <code>"educated"</code> has period 6 in addition to the trivial periods of 8 and above. The minimum period of {{math|''x''}} is denoted as {{math|''p(x)''}}.
* A '''repetition''' {{math|''w''}} in {{math|''(u,v)''}} is a non-empty string such that:
** {{math|''w''}} is a suffix of {{math|''u''}} or {{math|''u''}} is a suffix of {{math|''w''}};
** {{math|''w''}} is a prefix of {{math|''v''}} or {{math|''v''}} is a prefix of {{math|''w''}};
*: In other words, {{math|''w''}} occurs on both sides of the cut with a possible overflow on either side. Examples include <code>"an"</code> for <code>("ban","ana")</code> and <code>"voca"</code> for <code>("a","vocado")</code>. Each factorization trivially has at least one repetition: the string {{math|''vu''}}.<ref name=igm-mlv/>
* A '''local period''' is the length of a repetition in {{math|''(u,v)''}}. The smallest local period in {{math|''(u,v)''}} is denoted as {{math|''r(u,v)''}}. Because the trivial repetition {{math|''vu''}} is guaranteed to exist and has the same length as {{math|''x''}}, we see that {{math|1 ≤ ''r(u,v)'' ≤ ''len(x)''}}.
* A '''critical factorization''' is a factorization {{math|''(u,v)''}} of {{math|''x''}} such that {{math|1=''r(u,v)'' = ''p(x)''}}. The existence of a critical factorization is provably guaranteed.<ref name=CP91/> For a needle of length {{math|''m''}} in an ordered alphabet, it can be computed in {{math|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>

== The algorithm ==
{{Missing information|section|the ''match'' function|date=March 2022}}

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 the [[Lyndon word#Generation|Duval's algorithm]], which is simpler and still linear time but slower in practice.<ref>{{cite journal |last1=Adamczyk |first1=Zbigniew |last2=Rytter |first2=Wojciech |title=A note on a simple computation of the maximal suffix of a string |journal=Journal of Discrete Algorithms |date=May 2013 |volume=20 |pages=61–64 |doi=10.1016/j.jda.2013.03.002|doi-access=free}}</ref>

 ''Shorthand for inversion.''
 '''function''' cmp(a, b)
     '''if''' a > b '''return''' 1
     '''if''' a = b '''return''' 0
     '''if''' a < b '''return''' -1
 
 '''function''' maxsuf(n, rev)
     l ← len(n)
     p ← 1       ''currently known period.''
     k ← 1       ''index for period testing, 0 < k <= p.''
     j ← 0       ''index for maxsuf testing. greater than maxs.''
     i ← -1      ''the proposed starting index of maxsuf''
     
     '''while''' j + k < l
         cmpv ← cmp(n[j + k], n[i + k])
         '''if''' rev
             cmpv ← -cmpv   ''invert the comparison''
         '''if''' cmpv < 0
             ''Suffix (j+k) is smaller. Period is the entire prefix so far.''
             j ← j + k
             k ← 1
             p ← j - i
         '''else if''' cmpv = 0
             ''They are the same - we should go on.''
             '''if''' k = 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]
 
 '''function''' crit_fact(n)
     [idx1, per1] ← maxsuf(n, false)
     [idx2, per2] ← maxsuf(n, true)
     '''if''' idx1 > 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.

 '''function''' match(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.''
     '''if''' n[0] ... n[l] = n[l+1] ... n[l+p]
         P ← {}
         pos ← 0
         s ← 0
         
     ''TODO. At least put the skip in.''

== References ==
{{reflist|35em}}
{{Strings}}

[[Category:String matching algorithms]]