Basics 0/97

String matching: KMP, Z-function and rolling hashes · 1 of 2 Advanced

KMP and the prefix function

Build the prefix function, use it to find every copy of a pattern in linear time, and read borders and periods from it.

3,224 words · 15 min read

Part 1 of 8 Pattern and text

String matching

Where does one string occur inside another? We call the short string the pattern and the long one the text, and string matching means finding every place where the pattern occurs as a contiguous piece of the text. Copies may overlap: aba occurs in ababa at indices 0 and 2, and the two copies share the middle a. CSES's String Matching asks for the number of copies.

You get a text of nn letters and a pattern of mm letters. Count the positions of the text where a copy of the pattern starts.

The first input line holds the text and the second the pattern. Print the count.

Constraints

  • 1≤n,m≤1061 \le n, m \le 10^6
  • Both strings use only the letters a to z.

Sample · Input

saippuakauppias
pp

Output

2

In the sample, pp starts at index 3 of saippuakauppias (sai·pp·uak) and again at index 10 (kau·pp·ias), so the answer is 2.

The direct method tries every start and compares up to mm letters at each one. To see how slow that can get, take a text of 10610^6 a's and a pattern of 99,999 a's followed by one b, so m=100,000m = 100{,}000. Every start matches 99,999 a's before the b fails, so the search makes

(n−m+1)×m=900,001×100,000≈9×1010 comparisons\begin{aligned} (n - m + 1) \times m &= 900{,}001 \times 100{,}000 \\ &\approx 9 \times 10^{10} \text{ comparisons} \end{aligned}

At a rough 10810^8 simple steps a second, that is about 900 seconds, or 15 minutes. Three tools find the copies in linear time. The prefix function and the Z-function reuse the letters already matched, so the search never steps back in the text; rolling hashes compare numbers computed from the letters instead. This page builds the prefix function and the search that runs on it, and the next two pages build the other two.

Where the direct search wastes work

def find_all(text, pattern):
    m = len(pattern)
    return [s for s in range(len(text) - m + 1) if text[s:s + m] == pattern]

find_all("saippuakauppias", "pp") returns [3, 10]. The slice comparison hides an inner loop of up to m letters for each start.

To see where the time goes, follow the search on the million a's. The first start matches 99,999 a's and fails when the pattern's b meets another a. The search then moves one step right and compares 99,998 of those same a's again, and every later start does the same, although the first start has already shown what those letters are. A faster search keeps the part of the match that can still begin a copy, and continues from the same text letter. To say which part that is, we need one definition.