KMP Algorithm Coding Problems: 2 Questions with Solutions

How kmp algorithm works, step by step

1. KMP first studies the pattern "ababc" on its own: lps[i] is the length of the longest proper prefix of p[0..i] that is also a suffix of it. lps[0] = 0. On a mismatch, this table says how much of the match so far can be kept.
2. p[1] = 'b' differs from p[0] = 'a', so no prefix of "ab" is also a suffix of it: lps[1] = 0.
3. p[2] = 'a' equals p[0], so the border grows to "a", which is both a prefix and a suffix of "aba": lps[2] = 1.
4. p[3] = 'b' equals p[1], so the border grows to "ab", which is both a prefix and a suffix of "abab": lps[3] = 2.
5. p[4] = 'c' ≠ p[2] = 'a', so len falls back to lps[1] = 0; 'c' ≠ p[0] = 'a' too, so lps[4] = 0. Falling back through the table is the same move the search will make.
6. i and j advance together while the characters agree: "abab" matches, but t[4] = 'a' is not p[4] = 'c'. Naive search would restart at index 1 and re-read the text; KMP keeps i at 4.
7. On a mismatch j falls back to lps[3] = 2: "abab" ends with "ab", the pattern's own start, so the pattern slides 2 places and those 2 characters count as matched without being read again. i stays at 4.
8. With "ab" already matched, comparing resumes at t[4] against p[2]: "a" matches, then t[5] = 'c' is not p[3] = 'b'.
9. Still at i = 5: j falls back to lps[2] = 1, but 'c' is not p[1] = 'b' either; then to lps[0] = 0, and 'c' is not p[0] = 'a'. No prefix of the pattern can end at index 5, so i moves on to 6 — forward, never back.
10. From i = 6: every character agrees and j reaches 5, the pattern's length. "ababc" occurs at index 6.
11. KMP finds "ababc" at index 6 with 14 character comparisons, where naive search makes 19. i never moves backwards and each fallback undoes an earlier step of j, so the search is O(n) after an O(m) table: O(n + m) in all.

KMP Algorithm study plan

All 2 KMP Algorithm problems (2 hard) over 2 days, about 1 h 55 min in all — the pattern first, then easiest to hardest. Then move on to Rolling Hash.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

• Longest Happy Prefix Hard

Day 2

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Shortest Palindrome Hard

Next topic: Rolling Hash

KMP Algorithm: the essentials

When to reach for it

A pattern in a long text where the naive scan could reach O(n × m) — and, more often in interviews, a question about borders, prefixes that are also suffixes: "the longest happy prefix", "the shortest palindrome by adding characters in front", "the smallest period", "is s one block repeated".

The pattern

pi[i] is the length of the longest proper prefix of s[:i + 1] that is also its suffix. Build it left to right: extend the previous border by one character, or on a mismatch fall back to the border's border, k = pi[k - 1], until it extends or reaches 0. To search, run it over pattern + "#" + text: a value equal to the pattern's length ends a match. For Shortest Palindrome, the last value over s + "#" + s[::-1] is the longest palindromic prefix. The smallest period is n - pi[n - 1].

def prefix_function(s):             # pi[i]: longest proper border of s[:i + 1]
    pi = [0] * len(s)
    for i in range(1, len(s)):
        k = pi[i - 1]               # the border we try to extend
        while k and s[i] != s[k]:
            k = pi[k - 1]           # fall back to the border's border
        if s[i] == s[k]:
            k += 1
        pi[i] = k
    return pi

Cost

O(n) time and space: k rises by at most one per character, so the fallbacks total at most n. A search is O(n + m), with O(m) space if the text streams against the pattern's table.

Common mistakes

• Counting the whole string as its own border; borders are proper, so pi[0] is 0.
• Falling back to pi[k] instead of pi[k - 1]; the length-k prefix's border sits at its last index.
• A separator that can occur in the input, so a border runs across the join.
• Resetting to 0 on a mismatch instead of falling back: it misses aab in aaab.

Start with

• Longest Happy Prefix: the table's last value.
• Shortest Palindrome: a border of the string joined to its reverse.

All kmp algorithm problems

Hard (2)

• Longest Happy Prefix String, Rolling Hash
• Shortest Palindrome String, Rolling Hash

Companies that ask kmp algorithm problems

• Amazon 2 problems on kmp algorithm
• Google 2 problems on kmp algorithm
• Microsoft 2 problems on kmp algorithm

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems