A variant of this algorithm is what glibc uses for its implementation of memmem. I say "variant" because it uses a shift table in some cases.
I found this original paper describing the algorithm to be notable, in particular for how rigorous it is. I've read it a couple of times so far, but I still don't grok everything. One thing I'm particularly interested in is trying to simplify the algorithm so that you don't need to handle the short and long period cases differently. In particular, the paper hints that this is possible:
> The string-matching algorithm of Section 2 uses the period of
the pattern. A previous computation of this period is possible.
This precomputation can be made easily by using Knuth, Morris,
and Pratt’s algorithm on the pattern. This precomputation,
combined with both the computation of a critical factorization
of the pattern and our string-matching algorithm, leads to an
algorithm that is globally linear in time and space. But, since
the string-matching algorithm operates in constant space, it
is desirable to improve on the precomputation of the period
of the pattern, with the aim of obtaining a global algorithm
that is in linear time and constant space. There are two ways
to achieve that goal. One is a direct computation of the
period by an algorithm operating in linear time and constant
space. Such an algorithm is described in . It can also be
obtained as a consequence of the results in . Our approach
here is different. We shall describe a modification of our
string-matching algorithm that avoids the use of the period of
the pattern, giving an algorithm that is linear time and constant
space on the whole. The point is that the exact value of the
period of the pattern is actually needed only when it is less
than half the length of the pattern. When the period of the
pattern is larger, an even simpler string-matching algorithm is
But they don't seem to explain why they went the route of approximating the period even when they cite algorithms that satisfy their desired complexity constraints (linear time, constant space). So my next task is to read the cited papers and hopefully discern for myself.
Very good stuff, I learned about the duality between borders and periods and I understand how the KMP algorithm requires O(m) (pattern length) space to construct the table, but the critical factorization only takes up 2 integers O(1) so it's a much more space efficient matching algorithm.