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 letters and a pattern of 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
- 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 letters at each one. To see how slow that can get, take a text of a's and a pattern of 99,999 a's followed by one b, so . Every start matches 99,999 a's before the b fails, so the search makes
At a rough 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.
Definition
A border of a string is a proper prefix that is also a suffix. A prefix starts at the beginning of the string, a suffix ends at its end, and proper means shorter than the whole string.
abab has the border ab: its first two letters equal its last two. aaa has two borders, a and aa. abc has none. Below, s[0..i] means the letters of from position 0 through position i, both included.
Why borders tell the search where to go next
Suppose the search has matched the first letters of the pattern and then fails. Consider moving the pattern places right, with . Its first letters then sit under the last matched letters, which equal the pattern's letters to . So the new start can work only if the first letters of the pattern equal its letters to : they must be a border of the matched letters.
A longer border means a shorter move, so the longest border gives the nearest start that can still work, and every start the move skips cannot match. If the matched letters have no border, no start inside them can work: the pattern moves past them, and the search compares the same text letter with the pattern's first letter.
The search can fail after any number of matched letters, so we want the longest border of every prefix of the pattern, ready before the search begins. The prefix function of a string stores exactly that: pi[i] is the length of the longest border of s[0..i]. Here it is for aabaaab.
| i | s[0..i] | Longest border | pi[i] |
|---|---|---|---|
| 0 | a | none | 0 |
| 1 | aa | a | 1 |
| 2 | aab | none | 0 |
| 3 | aaba | a | 1 |
| 4 | aabaa | aa | 2 |
| 5 | aabaaa | aa | 2 |
| 6 | aabaaab | aab | 3 |
A border is shorter than its string, so a single letter has none and pi[0] is 0.
Let's watch one skip happen, on text abababc and pattern ababc. Start 0 matches abab and fails on the fifth letter. The longest border of abab is ab, so we slide the pattern until its first ab sits under the last ab that already matched. The next comparison is at the same text letter, index 4.
bab to equal aba, which fails, and no comparison is spent on it.How is the prefix function built?
The skip only pays off if the table is cheap to build. We fill it left to right, and each value comes from values already in the table. Suppose pi[i - 1] = : the first letters of equal the letters that end at position . Take any border of s[0..i] and drop the last letter from both of its copies, the one at the start of and the one ending at position i. The shortened copies are still equal, and the second now ends at position , so they form a border of s[0..i - 1], an empty one if the border had a single letter.
So every border of s[0..i] is a border of s[0..i - 1] extended by the letter s[i], if we count the empty border, of length 0. We try the longest one first, of length . Its copy at the start is followed by s[j], so it extends exactly when s[i] equals s[j], and then the border grows to . Nothing longer is possible, because it would need a border of s[0..i - 1] longer than .
If s[i] differs from s[j], we try the next shorter border of s[0..i - 1]. A shorter border sits at the start of , so it also sits at the start of the first letters, and it sits at the end of s[0..i - 1], so it also sits at the end of the last letters. Those two blocks of letters are the same string, s[0..j - 1], so every shorter border is a border of s[0..j - 1], and every border of s[0..j - 1] is one of them. So the next shorter border is the longest border of s[0..j - 1], and its length is pi[j - 1], already in the table. We set to it and compare again:
def prefix_function(s):
pi = [0] * len(s)
for i in range(1, len(s)):
j = pi[i - 1]
while j > 0 and s[i] != s[j]:
j = pi[j - 1]
if s[i] == s[j]:
j += 1
pi[i] = j
return piprefix_function("aabaaab") returns [0, 1, 0, 1, 2, 2, 3].
The answer is right because the chain , pi[j - 1], … visits every border of s[0..i - 1] from longest to shortest: every shorter border is a border of the longest one. So the first border that s[i] extends gives the longest border of s[0..i]. When reaches 0, only the empty border is left: we compare s[i] with s[0] once, and the value is 1 or 0.
Fill the prefix function one cell at a time
Let's run the build on aabaaab. Each cell starts from the value on its left and compares one pair of letters. A match grows the border by one; a mismatch falls back to a shorter border and compares again, and the line under the table lists every j tried. Try a pattern of your own, such as abcabcab: the values climb by one once the repeat starts.
Position 5 is the first cell where a fallback ends in a match. The cell on its left says 2, so the build compares s[5] with s[2]: a against b. It falls back to pi[1] = 1, compares a with a, and stores 2.
Why the build takes linear time
One position can fall back several times. In aaab, the b at position 3 tries , then 1, then 0, so the loop inside a loop looks like . Counting the changes to over the whole string gives a better bound. Each step starts from pi[i - 1], the value the step before ended with, so carries over from one position to the next. Each position raises by at most 1, each fallback lowers it by at least 1, and starts at 0 and never goes below 0. So cannot fall back more times than it was raised, which gives
and the two loops together run their bodies fewer than times: .
How does the prefix function find the pattern?
The simplest way to search the text with the prefix function is to join pattern and text into one string, s = pattern + "#" + text, with a separator that appears in neither, and build the prefix function of all of it. A prefix of longer than the pattern contains the #, and the only # in is the one right after the pattern, so no later stretch of equals that prefix. Every value is therefore at most , and pi[i] = means a copy of the pattern ends at position i.
The text starts at position of , so position i of is text index . The copy ends there and has letters, so it starts places earlier, at text index
Let's check it on pattern abab and text abababcabab. The joined string abab#abababcabab reaches 4 at positions 8, 10 and 15, so the copies start at , 2 and 7. String Matching only needs the count:
def prefix_function(s):
pi = [0] * len(s)
for i in range(1, len(s)):
j = pi[i - 1]
while j > 0 and s[i] != s[j]:
j = pi[j - 1]
if s[i] == s[j]:
j += 1
pi[i] = j
return pi
def count_matches(text, pattern):
m = len(pattern)
pi = prefix_function(pattern + "#" + text)
return sum(1 for value in pi if value == m)
text = input()
pattern = input()
print(count_matches(text, pattern))On the sample, the program prints 2.
On the million a's, the joined string has letters and the loop body runs fewer than twice per letter, so the search takes at most about 2.2 million steps instead of 90 billion comparisons.
Step through the search on pattern # text
Here is the same stepper on abab#abababcabab. The cells over the text say how much of the pattern ends at each letter, and a cell that reaches 4 turns green. Watch position 9: the value drops from 4 to 3 without starting over. The border ab of abab lets the next copy start two letters later, and that is how the search finds the overlapping copy at index 2.
Worked example
Trace the search on chosen inputs
The trace fills pi on pattern # text, one position per step, and lists every j it tries. Besides the running example, it can search for aa in aaaaa, where a copy ends at every letter after the first; for abab in ababbab, where one position falls back from 4 to 2 to 0; and for aab in aaab, where the only copy begins inside a failed attempt.
Join the pattern, a #, and the text: s = "abab#abababcabab". The # appears in neither string, so no border can run across it. pi[0] is 0, and a match ends wherever pi reaches m = 4.
- m
- 4
- matches so far
- none
Change the example input
Current result: [0,2,7]
Search without joining the strings
Given strings haystack and needle, return the index where needle first occurs in haystack, or -1 if it does not occur.
Constraints
-
haystack.length,needle.length - Both strings use only lowercase English letters.
Sample 1 · Input
haystack = "sadbutsad", needle = "sad"
Output
0
Sample 2 · Input
haystack = "leetcode", needle = "leeto"
Output
-1
The joined string stores a table entry for every text letter, but each step reads only the entry just before it, which one variable can hold. Its fallbacks read pi[j - 1] with , one of the first entries, and those depend only on the pattern: they are the pattern's own prefix function. So we keep just , the number of pattern letters matched so far, and read the text one letter at a time. A mismatch falls back along the pattern's table exactly as the build does, and a match grows by one. When reaches , a copy ends at the current letter.
This form, with one index in the text and one in the pattern, is the Knuth-Morris-Pratt algorithm, or KMP. It stores only the pattern's table values, however long the text is.
def str_str(haystack, needle):
pi = prefix_function(needle)
j = 0
for i, ch in enumerate(haystack):
while j > 0 and ch != needle[j]:
j = pi[j - 1]
if ch == needle[j]:
j += 1
if j == len(needle):
return i - len(needle) + 1
return -1str_str("sadbutsad", "sad") returns 0; str_str("leetcode", "leeto") returns -1. It uses prefix_function from above.
To find every copy instead of only the first, set j = pi[m - 1] after recording a match, before reading the next letter. That keeps the longest border of the pattern, which may begin an overlapping copy. For aa in aaaa the search finds starts 0, 1 and 2, where resetting j to 0 would miss start 1.
Deeper read: empty patterns and very long texts
The code above assumes a nonempty pattern. An empty pattern needs a rule of its own. Python counts it at every position from 0 through n, so "abc".count("") is 4, and find in both Python and C++ returns 0 for it. A pattern longer than the text has no match.
Because the two-index form keeps only the pattern's table, it can also read a text too large to hold in memory, one letter at a time.
What does the prefix function say about repetition?
So far we have used the prefix function to search. It also tells us something about a single string: whether it repeats. A period of is a shift with s[i] = s[i + p] wherever both exist. Shifting by lines the first letters up with the last , so is a period exactly when has a border of length . The longest border therefore gives the shortest period:
abcabcabc, , the longest border has length 6 and the shortest period is .Test whether a string repeats one block
Given a string s, decide whether it can be built by joining two or more copies of one of its substrings.
Constraints
-
s.length suses only lowercase English letters.
Sample 1 · Input
s = "abab"
Output
true
Sample 2 · Input
s = "aba"
Output
false
Sample 3 · Input
s = "abcabcabcabc"
Output
true
A period alone is not enough. abcab has period 3, but 3 does not divide 5, so it is not whole copies of abc. With the shortest period, is two or more copies of its first letters exactly when divides and . For abab, , which divides 4, so the answer is true.
def repeated_substring_pattern(s):
n = len(s)
p = n - prefix_function(s)[-1]
return p < n and n % p == 0repeated_substring_pattern("abab") returns True; repeated_substring_pattern("aba") returns False.
Deeper read: why the shortest period is the one to test
Suppose is copies of some block of length . Then is a period, divides and . Fine and Wilf's periodicity lemma says that two periods and with combine into a period of length , and the condition holds here: because is the shortest period, so . That period is no longer than , and is the shortest period, so : divides , and because divides , so does . So whenever some block works, the shortest period divides and the test answers true.
Read the longest border directly
A happy prefix is a nonempty prefix of s that is also a suffix, other than s itself. Return the longest happy prefix, or the empty string if there is none.
Constraints
-
s.length suses only lowercase English letters.
Sample 1 · Input
s = "level"
Output
"l"
Sample 2 · Input
s = "ababab"
Output
"abab"
A happy prefix is a nonempty border, so the longest one is the first pi[n - 1] letters, s[:prefix_function(s)[-1]]. For ababab the table ends in 4, and the answer is abab.
Find the longest palindromic prefix with one table
You may add letters only in front of s. Return the shortest palindrome you can make this way.
Constraints
-
s.length suses only lowercase English letters.
Sample 1 · Input
s = "aacecaaa"
Output
"aaacecaaa"
Sample 2 · Input
s = "abcd"
Output
"dcbabcd"
Say has letters and we add letters in front of it. The first letters of the palindrome mirror its last , which are the last letters of , so the added letters are those letters reversed. Between the two mirrored ends sits the rest of , its first letters, and the middle of a palindrome also reads the same both ways. So adding letters works exactly when the first letters of form a palindrome, and the fewest letters come from keeping the longest prefix that is already a palindrome and putting the reverse of the rest in front. For aacecaaa that prefix is aacecaa, and the rest is one a.
To find that prefix quickly, write rev for reversed. The last letters of rev are the first letters of reversed, so a prefix of is a palindrome exactly when it is also a suffix of rev. The last value of the prefix function of s + "#" + rev is therefore the length of the longest palindromic prefix. The # keeps that value from exceeding , and when is empty it still gives the table one entry for the code to read.
def shortest_palindrome(s):
rev = s[::-1]
keep = prefix_function(s + "#" + rev)[-1]
return rev[:len(s) - keep] + sshortest_palindrome("aacecaaa") returns "aaacecaaa"; shortest_palindrome("abcd") returns "dcbabcd".
Prefix function and KMP time and space
- Direct search
- Up to comparisons at each of starts.
- Prefix function
time and space - falls at most as often as it rises.
- Search on pattern # text
- One prefix function over letters.
- Two-index KMP
time, space - Only the pattern's table is stored.
Common mistakes
After a mismatch, setting j back to 0 and moving to the next text letter.
- Where it breaks
- Text
aaab, patternaab: the search matchesaa, fails on the third a, resets, and returns[]instead of[1]. - The fix
- Fall back to
pi[j - 1]and compare the same text letter again.
Falling back once with
ifinstead of looping withwhile.- Where it breaks
- Text
aabaa, patternaaa, two-index form: after the b, j should fall from 2 to 1 to 0. One fallback stops at 1, and the search reports a copy at index 2 that is not there. - The fix
- Repeat the fallback until the letters match or j is 0.
Joining pattern and text without a separator.
- Where it breaks
- Pattern
aa, textaaa: the joinedaaaaahas pi = [0, 1, 2, 3, 4], so borders grow past . A check for pi == 2 fires only at position 2, where the match straddles the pattern and the text, and misses both real copies. - The fix
- Put a character that appears in neither string between them, such as #.
Reading any period as a whole number of repeats.
- Where it breaks
abcabhas period 3, so a period-only check answers true; Repeated Substring Pattern must return false.- The fix
- Check that and
n % p == 0.
Recall Why does a fallback compare the same text letter again?
Because that letter has not matched anything yet. A fallback only changes how much of the earlier text counts as matched, and the current letter may extend the shorter border even though it failed to extend the longer one. On text aaab with pattern aab, the a at index 2 cannot extend aa to aab, but after falling back to a it extends that to aa, and the b completes the copy at index 1.