xref: /third_party/python/Objects/stringlib/stringlib_find_two_way_notes.txt

This document explains Crochemore and Perrin's Two-Way string matching
algorithm, in which a smaller string (the "pattern" or "needle")
is searched for in a longer string (the "text" or "haystack"),
determining whether the needle is a substring of the haystack, and if
so, at what index(es). It is to be used by Python's string
(and bytes-like) objects when calling `find`, `index`, `__contains__`,
or implicitly in methods like `replace` or `partition`.

This is essentially a re-telling of the paper

    Crochemore M., Perrin D., 1991, Two-way string-matching,
        Journal of the ACM 38(3):651-675.

focused more on understanding and examples than on rigor. See also
the code sample here:

    http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260

The algorithm runs in O(len(needle) + len(haystack)) time and with
O(1) space. However, since there is a larger preprocessing cost than
simpler algorithms, this Two-Way algorithm is to be used only when the
needle and haystack lengths meet certain thresholds.


These are the basic steps of the algorithm:

    * "Very carefully" cut the needle in two.
    * For each alignment attempted:
        1. match the right part
            * On failure, jump by the amount matched + 1
        2. then match the left part.
            * On failure jump by max(len(left), len(right)) + 1
    * If the needle is periodic, don't re-do comparisons; maintain
      a "memory" of how many characters you already know match.


-------- Matching the right part --------

We first scan the right part of the needle to check if it matches the
the aligned characters in the haystack. We scan left-to-right,
and if a mismatch occurs, we jump ahead by the amount matched plus 1.

Example:

       text:    ........EFGX...................
    pattern:    ....abcdEFGH....
        cut:        <<<<>>>>

Matched 3, so jump ahead by 4:

       text:    ........EFGX...................
    pattern:        ....abcdEFGH....
        cut:            <<<<>>>>

Why are we allowed to do this? Because we cut the needle very
carefully, in such a way that if the cut is ...abcd + EFGH... then
we have

        d != E
       cd != EF
      bcd != EFG
     abcd != EFGH
          ... and so on.

If this is true for every pair of equal-length substrings around the
cut, then the following alignments do not work, so we can skip them:

       text:    ........EFG....................
    pattern:     ....abcdEFGH....
                        ^   (Bad because d != E)
       text:    ........EFG....................
    pattern:      ....abcdEFGH....
                        ^^   (Bad because cd != EF)
       text:    ........EFG....................
    pattern:       ....abcdEFGH....
                        ^^^   (Bad because bcd != EFG)

Skip 3 alignments => increment alignment by 4.


-------- If len(left_part) < len(right_part) --------

Above is the core idea, and it begins to suggest how the algorithm can
be linear-time. There is one bit of subtlety involving what to do
around the end of the needle: if the left half is shorter than the
right, then we could run into something like this:

       text:    .....EFG......
    pattern:       cdEFGH

The same argument holds that we can skip ahead by 4, so long as

       d != E
      cd != EF
     ?cd != EFG
    ??cd != EFGH
         etc.

The question marks represent "wildcards" that always match; they're
outside the limits of the needle, so there's no way for them to
invalidate a match. To ensure that the inequalities above are always
true, we need them to be true for all possible '?' values. We thus
need cd != FG and cd != GH, etc.


-------- Matching the left part --------

Once we have ensured the right part matches, we scan the left part
(order doesn't matter, but traditionally right-to-left), and if we
find a mismatch, we jump ahead by
max(len(left_part), len(right_part)) + 1. That we can jump by
at least len(right_part) + 1 we have already seen:

       text: .....EFG.....
    pattern:  abcdEFG
    Matched 3, so jump by 4,
    using the fact that d != E, cd != EF, and bcd != EFG.

But we can also jump by at least len(left_part) + 1:

       text: ....cdEF.....
    pattern:   abcdEF
    Jump by len('abcd') + 1 = 5.

    Skip the alignments:
       text: ....cdEF.....
    pattern:    abcdEF
       text: ....cdEF.....
    pattern:     abcdEF
       text: ....cdEF.....
    pattern:      abcdEF
       text: ....cdEF.....
    pattern:       abcdEF

This requires the following facts:
       d != E
      cd != EF
     bcd != EF?
    abcd != EF??
         etc., for all values of ?s, as above.

If we have both sets of inequalities, then we can indeed jump by
max(len(left_part), len(right_part)) + 1. Under the assumption of such
a nice splitting of the needle, we now have enough to prove linear
time for the search: consider the forward-progress/comparisons ratio
at each alignment position. If a mismatch occurs in the right part,
the ratio is 1 position forward per comparison. On the other hand,
if a mismatch occurs in the left half, we advance by more than
len(needle)//2 positions for at most len(needle) comparisons,
so this ratio is more than 1/2. This average "movement speed" is
bounded below by the constant "1 position per 2 comparisons", so we
have linear time.


-------- The periodic case --------

The sets of inequalities listed so far seem too good to be true in
the general case. Indeed, they fail when a needle is periodic:
there's no way to split 'AAbAAbAAbA' in two such that

    (the stuff n characters to the left of the split)
    cannot equal
    (the stuff n characters to the right of the split)
    for all n.

This is because no matter how you cut it, you'll get
s[cut-3:cut] == s[cut:cut+3]. So what do we do? We still cut the
needle in two so that n can be as big as possible. If we were to
split it as

    AAbA + AbAAbA

then A == A at the split, so this is bad (we failed at length 1), but
if we split it as

    AA + bAAbAAbA

we at least have A != b and AA != bA, and we fail at length 3
since ?AA == bAA. We already knew that a cut to make length-3
mismatch was impossible due to the period, but we now see that the
bound is sharp; we can get length-1 and length-2 to mismatch.

This is exactly the content of the *critical factorization theorem*:
that no matter the period of the original needle, you can cut it in
such a way that (with the appropriate question marks),
needle[cut-k:cut] mismatches needle[cut:cut+k] for all k < the period.

Even "non-periodic" strings are periodic with a period equal to
their length, so for such needles, the CFT already guarantees that
the algorithm described so far will work, since we can cut the needle
so that the length-k chunks on either side of the cut mismatch for all
k < len(needle). Looking closer at the algorithm, we only actually
require that k go up to max(len(left_part), len(right_part)).
So long as the period exceeds that, we're good.

The more general shorter-period case is a bit harder. The essentials
are the same, except we use the periodicity to our advantage by
"remembering" periods that we've already compared. In our running
example, say we're computing

    "AAbAAbAAbA" in "bbbAbbAAbAAbAAbbbAAbAAbAAbAA".

We cut as AA + bAAbAAbA, and then the algorithm runs as follows:

    First alignment:
    bbbAbbAAbAAbAAbbbAAbAAbAAbAA
    AAbAAbAAbA
      ^^X
    - Mismatch at third position, so jump by 3.
    - This requires that A!=b and AA != bA.

    Second alignment:
    bbbAbbAAbAAbAAbbbAAbAAbAAbAA
       AAbAAbAAbA
         ^^^^^^^^
        X
    - Matched entire right part
    - Mismatch at left part.
    - Jump forward a period, remembering the existing comparisons

    Third alignment:
    bbbAbbAAbAAbAAbbbAAbAAbAAbAA
          AAbAAbAAbA
          mmmmmmm^^X
    - There's "memory": a bunch of characters were already matched.
    - Two more characters match beyond that.
    - The 8th character of the right part mismatched, so jump by 8
    - The above rule is more complicated than usual: we don't have
      the right inequalities for lengths 1 through 7, but we do have
      shifted copies of the length-1 and length-2 inequalities,
      along with knowledge of the mismatch. We can skip all of these
      alignments at once:

        bbbAbbAAbAAbAAbbbAAbAAbAAbAA
               AAbAAbAAbA
                ~                   A != b at the cut
        bbbAbbAAbAAbAAbbbAAbAAbAAbAA
                AAbAAbAAbA
                ~~                  AA != bA at the cut
        bbbAbbAAbAAbAAbbbAAbAAbAAbAA
                 AAbAAbAAbA
                 ^^^^X              7-3=4 match, and the 5th misses.
        bbbAbbAAbAAbAAbbbAAbAAbAAbAA
                  AAbAAbAAbA
                   ~                A != b at the cut
        bbbAbbAAbAAbAAbbbAAbAAbAAbAA
                   AAbAAbAAbA
                   ~~               AA != bA at the cut
        bbbAbbAAbAAbAAbbbAAbAAbAAbAA
                    AAbAAbAAbA
                      ^X            7-3-3=1 match and the 2nd misses.
        bbbAbbAAbAAbAAbbbAAbAAbAAbAA
                     AAbAAbAAbA
                      ~             A != b at the cut

    Fourth alignment:
    bbbAbbAAbAAbAAbbbAAbAAbAAbAA
                 AAbAAbAAbA
                   ^X
    - Second character mismatches, so jump by 2.

    Fifth alignment:
    bbbAbbAAbAAbAAbbbAAbAAbAAbAA
                  AAbAAbAAbA
                    ^^^^^^^^
                   X
    - Right half matches, so use memory and skip ahead by period=3

    Sixth alignment:
    bbbAbbAAbAAbAAbbbAAbAAbAAbAA
                     AAbAAbAAbA
                     mmmmmmmm^^
    - Right part matches, left part is remembered, found a match!

The one tricky skip by 8 here generalizes: if we have a period of p,
then the CFT says we can ensure the cut has the inequality property
for lengths 1 through p-1, and jumping by p would line up the
matching characters and mismatched character one period earlier.
Inductively, this proves that we can skip by the number of characters
matched in the right half, plus 1, just as in the original algorithm.

To make it explicit, the memory is set whenever the entire right part
is matched and is then used as a starting point in the next alignment.
In such a case, the alignment jumps forward one period, and the right
half matches all except possibly the last period. Additionally,
if we cut so that the left part has a length strictly less than the
period (we always can!), then we can know that the left part already
matches. The memory is reset to 0 whenever there is a mismatch in the
right part.

To prove linearity for the periodic case, note that if a right-part
character mismatches, then we advance forward 1 unit per comparison.
On the other hand, if the entire right part matches, then the skipping
forward by one period "defers" some of the comparisons to the next
alignment, where they will then be spent at the usual rate of
one comparison per step forward. Even if left-half comparisons
are always "wasted", they constitute less than half of all
comparisons, so the average rate is certainly at least 1 move forward
per 2 comparisons.


-------- When to choose the periodic algorithm ---------

The periodic algorithm is always valid but has an overhead of one
more "memory" register and some memory computation steps, so the
here-described-first non-periodic/long-period algorithm -- skipping by
max(len(left_part), len(right_part)) + 1 rather than the period --
should be preferred when possible.

Interestingly, the long-period algorithm does not require an exact
computation of the period; it works even with some long-period, but
undeniably "periodic" needles:

    Cut: AbcdefAbc == Abcde + fAbc

This cut gives these inequalities:

                 e != f
                de != fA
               cde != fAb
              bcde != fAbc
             Abcde != fAbc?
    The first failure is a period long, per the CFT:
            ?Abcde == fAbc??

A sufficient condition for using the long-period algorithm is having
the period of the needle be greater than
max(len(left_part), len(right_part)). This way, after choosing a good
split, we get all of the max(len(left_part), len(right_part))
inequalities around the cut that were required in the long-period
version of the algorithm.

With all of this in mind, here's how we choose:

    (1) Choose a "critical factorization" of the needle -- a cut
        where we have period minus 1 inequalities in a row.
        More specifically, choose a cut so that the left_part
        is less than one period long.
    (2) Determine the period P_r of the right_part.
    (3) Check if the left part is just an extension of the pattern of
        the right part, so that the whole needle has period P_r.
        Explicitly, check if
            needle[0:cut] == needle[0+P_r:cut+P_r]
        If so, we use the periodic algorithm. If not equal, we use the
        long-period algorithm.

Note that if equality holds in (3), then the period of the whole
string is P_r. On the other hand, suppose equality does not hold.
The period of the needle is then strictly greater than P_r. Here's
a general fact:

    If p is a substring of s and p has period r, then the period
    of s is either equal to r or greater than len(p).

We know that needle_period != P_r,
and therefore needle_period > len(right_part).
Additionally, we'll choose the cut (see below)
so that len(left_part) < needle_period.

Thus, in the case where equality does not hold, we have that
needle_period >= max(len(left_part), len(right_part)) + 1,
so the long-period algorithm works, but otherwise, we know the period
of the needle.

Note that this decision process doesn't always require an exact
computation of the period -- we can get away with only computing P_r!


-------- Computing the cut --------

Our remaining tasks are now to compute a cut of the needle with as
many inequalities as possible, ensuring that cut < needle_period.
Meanwhile, we must also compute the period P_r of the right_part.

The computation is relatively simple, essentially doing this:

    suffix1 = max(needle[i:] for i in range(len(needle)))
    suffix2 = ... # the same as above, but invert the alphabet
    cut1 = len(needle) - len(suffix1)
    cut2 = len(needle) - len(suffix2)
    cut = max(cut1, cut2) # the later cut

For cut2, "invert the alphabet" is different than saying min(...),
since in lexicographic order, we still put "py" < "python", even
if the alphabet is inverted. Computing these, along with the method
of computing the period of the right half, is easiest to read directly
from the source code in fastsearch.h, in which these are computed
in linear time.

Crochemore & Perrin's Theorem 3.1 give that "cut" above is a
critical factorization less than the period, but a very brief sketch
of their proof goes something like this (this is far from complete):

    * If this cut splits the needle as some
      needle == (a + w) + (w + b), meaning there's a bad equality
      w == w, it's impossible for w + b to be bigger than both
      b and w + w + b, so this can't happen. We thus have all of
      the ineuqalities with no question marks.
    * By maximality, the right part is not a substring of the left
      part. Thus, we have all of the inequalities involving no
      left-side question marks.
    * If you have all of the inequalities without right-side question
      marks, we have a critical factorization.
    * If one such inequality fails, then there's a smaller period,
      but the factorization is nonetheless critical. Here's where
      you need the redundancy coming from computing both cuts and
      choosing the later one.


-------- Some more Bells and Whistles --------

Beyond Crochemore & Perrin's original algorithm, we can use a couple
more tricks for speed in fastsearch.h:

    1. Even though C&P has a best-case O(n/m) time, this doesn't occur
       very often, so we add a Boyer-Moore bad character table to
       achieve sublinear time in more cases.

    2. The prework of computing the cut/period is expensive per
       needle character, so we shouldn't do it if it won't pay off.
       For this reason, if the needle and haystack are long enough,
       only automatically start with two-way if the needle's length
       is a small percentage of the length of the haystack.

    3. In cases where the needle and haystack are large but the needle
       makes up a significant percentage of the length of the
       haystack, don't pay the expensive two-way preprocessing cost
       if you don't need to. Instead, keep track of how many
       character comparisons are equal, and if that exceeds
       O(len(needle)), then pay that cost, since the simpler algorithm
       isn't doing very well.