Chapter 65 of 65

String Pattern Matching (KMP & Rabin-Karp)

On this page

Every time you press Ctrl + F in a browser, type a word, and see all its occurrences light up, a program is solving one question: where does this small string appear inside this big string?

The same question sits behind searching code in an IDE, filtering logs with grep, spam and virus scanners looking for known signatures, plagiarism checkers, and DNA researchers searching for a gene sequence among billions of letters.

This problem is called string pattern matching.

Given a text of length n and a pattern of length m, string pattern matching finds every position in the text where the pattern occurs as a contiguous substring.

text    = "ABABDABABCABAB"     (n = 14)
pattern = "ABAB"               (m = 4)

Answer: the pattern starts at indexes 0, 5 and 10

The simple approach is O(n × m) in the worst case. In this chapter, we learn two classic algorithms that do better:

KMP (Knuth-Morris-Pratt) → never re-reads the text, guaranteed O(n + m)
Rabin-Karp               → compares hashes instead of strings, O(n + m) on average

This chapter builds on Strings, Hashing and the Sliding Window technique. Note the difference from the previous chapter: DP on strings worked with subsequences and similarity, while pattern matching looks for an exact, contiguous match.


The Naive (Brute-Force) Approach

Place the pattern at every possible starting position (called a shift) and compare character by character:

text:    A B A B D A B A B C A B A B
shift 0: A B A B                        ✓ match at 0
shift 1:   A                            ✗ (B ≠ A)
shift 2:     A B A                      ✗ (D ≠ A)
shift 3:       A                        ✗ (B ≠ A)
shift 4:         A                      ✗ (D ≠ A)
shift 5:           A B A B              ✓ match at 5
  ...
import java.util.ArrayList;
import java.util.List;

class Main {

    // Returns every index where pattern starts in text
    static List<Integer> naiveSearch(String text, String pattern) {

        List<Integer> result = new ArrayList<>();
        int n = text.length();
        int m = pattern.length();

        for (int s = 0; s <= n - m; s++) {        // try every starting shift

            int j = 0;
            while (j < m && text.charAt(s + j) == pattern.charAt(j)) {
                j++;
            }

            if (j == m) {                         // all m characters matched
                result.add(s);
            }
        }
        return result;
    }

    public static void main(String[] args) {

        System.out.println(naiveSearch("ABABDABABCABAB", "ABAB"));
        System.out.println(naiveSearch("AAAAA", "AA"));
        System.out.println(naiveSearch("HELLO", "XYZ"));
    }
}

Output:

[0, 5, 10]
[0, 1, 2, 3]
[]

Notice that matches can overlap: "AA" occurs 4 times in "AAAAA".

Why the Naive Approach Can Be Slow

There are n - m + 1 shifts, and each one may compare up to m characters. The worst case looks like this:

text    = "AAAAAAAAAAAAAAAAAAAA"
pattern = "AAAAB"

At every shift, the first 4 characters match and only the 5th fails.
Total comparisons ≈ (n - m + 1) × m  →  O(n × m)

The real waste is this: after matching "AAAA" at one shift, the algorithm forgets everything and starts again at the next shift, re-reading characters it has already seen. KMP fixes exactly this.

Case

Time

Best / typical text (mismatch on the first character most of the time)

O(n)

Worst (long partial matches, like the example above)

O(n × m)

Extra space

O(1)

For everyday Java code, text.indexOf(pattern) and text.contains(pattern) are perfectly fine. Interviews and competitive programming, however, want an algorithm with a guaranteed bound, and they often ask you to implement and explain one.


KMP: The Key Idea

The Knuth-Morris-Pratt (KMP) algorithm, published in 1977, never moves backwards in the text. When a mismatch happens, it uses what it already knows about the pattern itself to decide how much of the match can be kept.

Look at this situation:

text:     A B A B A B C
pattern:  A B A B C
          ✓ ✓ ✓ ✓ ✗       4 characters matched, then A ≠ C

We have just matched "ABAB". Its last two characters "AB" are the same as the first two characters of the pattern. So instead of starting over, we can slide the pattern so that its prefix "AB" lines up with the "AB" we just read:

text:     A B A B A B C
pattern:      A B A B C
              ✓ ✓              already known to match, no need to re-check
                  ↑
          continue comparing from here (text index 4, pattern index 2)

The text pointer stays where it was. Only the pattern pointer jumps back, from 4 to 2. To know how far to jump for every possible mismatch, KMP precomputes a small table from the pattern: the LPS array.


The LPS Array

Two definitions first:

  • A proper prefix is a prefix that is not the whole string. For "ABAB": "A", "AB", "ABA".

  • A proper suffix is a suffix that is not the whole string. For "ABAB": "B", "AB", "BAB".

lps[i] is the length of the Longest proper Prefix of pattern[0..i] that is also a Suffix of pattern[0..i].

(Some books call it the prefix function or the failure function, and such a prefix-that-is-also-a-suffix is called a border.)

For "ABAB", the common prefix/suffix is "AB", so the value for the last index is 2. Here is the full array for pattern = "ABABCABAB":

i

pattern[0..i]

Longest border

lps[i]

0

A

(none, a proper prefix can't be the whole string)

0

1

AB

(none)

0

2

ABA

A

1

3

ABAB

AB

2

4

ABABC

(none)

0

5

ABABCA

A

1

6

ABABCAB

AB

2

7

ABABCABA

ABA

3

8

ABABCABAB

ABAB

4

pattern = A B A B C A B A B
lps     = 0 0 1 2 0 1 2 3 4

A few more to build intuition:

"AAAA"         → [0, 1, 2, 3]
"ABCDE"        → [0, 0, 0, 0, 0]      (all different: no borders)
"AABAACAABAA"  → [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

Building the LPS Array in O(m)

Checking every prefix against every suffix would be slow. Instead, we build the array from left to right, reusing earlier values. We keep len, the length of the current border, and compare pattern[i] with pattern[len]:

pattern[i] == pattern[len]  → the border grows: len++, lps[i] = len, i++
mismatch and len > 0        → fall back: len = lps[len - 1]  (try a shorter border, same i)
mismatch and len == 0       → no border: lps[i] = 0, i++

The fall-back step is the clever part. Let's trace pattern = "AABAAAB", which needs it:

index:    0 1 2 3 4 5 6
pattern:  A A B A A A B

i=1: p[1]=A vs p[0]=A  match    → len=1, lps[1]=1
i=2: p[2]=B vs p[1]=A  mismatch → len = lps[0] = 0
i=2: p[2]=B vs p[0]=A  mismatch, len=0 → lps[2]=0
i=3: p[3]=A vs p[0]=A  match    → len=1, lps[3]=1
i=4: p[4]=A vs p[1]=A  match    → len=2, lps[4]=2
i=5: p[5]=A vs p[2]=B  mismatch → len = lps[1] = 1      ← fall back
i=5: p[5]=A vs p[1]=A  match    → len=2, lps[5]=2
i=6: p[6]=B vs p[2]=B  match    → len=3, lps[6]=3

lps = [0, 1, 0, 1, 2, 2, 3]

At i = 5, the border "AA" could not be extended to "AAB". Instead of giving up, we asked: "what is the longest border of "AA"?" That is lps[1] = 1, the border "A". Extending "A" with A works, giving "AA" and lps[5] = 2.


KMP Search Step by Step

The search uses the same three rules, but compares the text with the pattern:

text[i] == pattern[j]  → i++, j++
                         if j == m: match found at i - m, then j = lps[m - 1]
mismatch and j > 0     → j = lps[j - 1]     (i does NOT move)
mismatch and j == 0    → i++

Let's trace text = "ABABABC" and pattern = "ABABC", with lps = [0, 0, 1, 2, 0]:

i=0, j=0: A == A → i=1, j=1
i=1, j=1: B == B → i=2, j=2
i=2, j=2: A == A → i=3, j=3
i=3, j=3: B == B → i=4, j=4
i=4, j=4: A vs C → mismatch, j = lps[3] = 2    (keep "AB", i stays at 4)
i=4, j=2: A == A → i=5, j=3
i=5, j=3: B == B → i=6, j=4
i=6, j=4: C == C → i=7, j=5 = m → MATCH at i - m = 2

The text pointer i only ever moved forward: 0, 1, 2, ..., 7. The naive approach would have gone back to shift 1 and then shift 2, re-reading text[2] and text[3]. KMP never does that.


KMP in Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Main {

    // lps[i] = length of the longest proper prefix of p[0..i]
    //          that is also a suffix of p[0..i]
    static int[] buildLPS(String p) {

        int m = p.length();
        int[] lps = new int[m];      // lps[0] is always 0
        int len = 0;                 // length of the current matching prefix
        int i = 1;

        while (i < m) {
            if (p.charAt(i) == p.charAt(len)) {
                len++;               // the border grows by one
                lps[i] = len;
                i++;
            } else if (len > 0) {
                len = lps[len - 1];  // fall back to a shorter border, retry same i
            } else {
                lps[i] = 0;          // no border at all
                i++;
            }
        }
        return lps;
    }

    static List<Integer> kmpSearch(String text, String pattern) {

        List<Integer> result = new ArrayList<>();
        int n = text.length();
        int m = pattern.length();
        int[] lps = buildLPS(pattern);

        int i = 0;   // index in text    (never moves backwards)
        int j = 0;   // index in pattern (= number of characters matched)

        while (i < n) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (j == m) {                 // full match
                    result.add(i - m);
                    j = lps[m - 1];           // keep going, allow overlaps
                }
            } else if (j > 0) {
                j = lps[j - 1];               // reuse what we already matched
            } else {
                i++;                          // nothing matched, move on
            }
        }
        return result;
    }

    public static void main(String[] args) {

        System.out.println("LPS of ABABCABAB: " + Arrays.toString(buildLPS("ABABCABAB")));

        System.out.println(kmpSearch("ABABABC", "ABABC"));
        System.out.println(kmpSearch("ABABDABACDABABCABAB", "ABABCABAB"));
        System.out.println(kmpSearch("AAAAA", "AA"));
    }
}

Output:

LPS of ABABCABAB: [0, 0, 1, 2, 0, 1, 2, 3, 4]
[2]
[10]
[0, 1, 2, 3]

After a full match, we set j = lps[m - 1] instead of 0. That is what lets KMP find overlapping matches like the four "AA"s in "AAAAA".

This code assumes a non-empty pattern. With an empty pattern, pattern.charAt(0) would throw, so handle that case separately if your problem allows it.

Why KMP Is O(n + m)

The search loop has a j = lps[j - 1] step that doesn't move i, so it is not obvious that it is linear. Here is the argument:

  • Every iteration either moves i forward (at most n times), or makes j smaller.

  • j only grows together with i, by 1 each time, so it grows at most n times in total.

  • j can never go below 0, so it can't shrink more than it grew: at most n shrinking steps.

Search loop iterations ≤ n + n = 2n   → O(n)
Building LPS (same argument on the pattern) → O(m)
Total                                        → O(n + m)
Extra space (the LPS array)                  → O(m)

This is the same kind of amortised reasoning you saw in the Sliding Window chapter, where an inner while loop still gave O(n) in total.

Seeing the Difference

Let's count character comparisons on the naive algorithm's worst case: a text of 10,000 As and a pattern of 99 As followed by one B.

class Main {

    static long naiveComparisons(String text, String pattern) {
        long count = 0;
        int n = text.length(), m = pattern.length();
        for (int s = 0; s <= n - m; s++) {
            int j = 0;
            while (j < m) {
                count++;
                if (text.charAt(s + j) != pattern.charAt(j)) break;
                j++;
            }
        }
        return count;
    }

    static long kmpComparisons(String text, String pattern) {
        long count = 0;
        int n = text.length(), m = pattern.length();

        int[] lps = new int[m];
        for (int i = 1, len = 0; i < m; ) {
            count++;
            if (pattern.charAt(i) == pattern.charAt(len)) lps[i++] = ++len;
            else if (len > 0) len = lps[len - 1];
            else lps[i++] = 0;
        }

        int i = 0, j = 0;
        while (i < n) {
            count++;
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (j == m) j = lps[m - 1];
            } else if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
        return count;
    }

    public static void main(String[] args) {

        String text = "A".repeat(10000);              // n = 10,000
        String pattern = "A".repeat(99) + "B";        // m = 100

        System.out.println("Naive comparisons: " + naiveComparisons(text, pattern));
        System.out.println("KMP comparisons:   " + kmpComparisons(text, pattern));
    }
}

Output:

Naive comparisons: 990100
KMP comparisons:   20098

The naive count is exactly (10000 - 100 + 1) × 100 = 990,100. KMP, including building its LPS array, stays within 2n + 2m = 20,200, almost 50 times fewer here. With a longer pattern, the gap grows even bigger.


Rabin-Karp: Matching with Hashes

Rabin-Karp (by Richard Karp and Michael Rabin, 1987) takes a completely different approach. Comparing two strings of length m costs O(m), but comparing two numbers costs O(1). So:

1. Turn the pattern into a number (its hash).
2. Turn each length-m window of the text into a number.
3. Only when the two numbers are equal, compare the actual characters.

The catch: computing the hash of each window from scratch would cost O(m) per window, which is no better than naive. The trick that makes Rabin-Karp work is the rolling hash.

The Rolling Hash Idea

Pretend the text is made of digits. Then each window is simply a number:

text = 2 3 5 9 0 2 3 1 4 1 5 ...      window size m = 5

window at s = 0: 23590
window at s = 1: 35902

We can get the next window from the previous one in O(1), just like a sliding window sum:

35902 = (23590 - 2 × 10⁴) × 10 + 2
          └──────┬──────┘   └─┬─┘  └┬┘
         remove the left   shift   add the new
         digit             left    right digit

For real strings, each character is treated as a "digit" in some base d (for example 256, the number of values a single byte can hold, which covers every ASCII character). The hash of a window c₀ c₁ ... cₘ₋₁ is:

hash = c₀·dᵐ⁻¹ + c₁·dᵐ⁻² + ... + cₘ₋₂·d + cₘ₋₁

These numbers quickly become far too large for a long, so everything is computed modulo a prime q:

h        = d^(m-1) mod q            (the weight of the leftmost character)
next     = ( d × (current - text[s] × h) + text[s + m] ) mod q

Because the result is taken modulo q, two different windows can end up with the same hash. That is a collision (see the Hashing chapter), and in Rabin-Karp it is called a spurious hit. This is why a hash match must always be confirmed by comparing the actual characters.


Worked Example: Rabin-Karp with q = 13

This is the classic textbook example. Using small numbers lets us follow every step by hand.

text    = 2359023141526739921
pattern = 31415
d = 10 (decimal digits), q = 13, m = 5

Pattern hash: 31415 mod 13 = 7
h = 10⁴ mod 13 = 3

Now slide a window of 5 digits over the text, rolling the hash each time:

class Main {

    public static void main(String[] args) {

        String text = "2359023141526739921";
        String pattern = "31415";
        int q = 13;          // a small prime, so we can follow the numbers
        int d = 10;          // base: decimal digits
        int n = text.length(), m = pattern.length();

        int h = 1;           // d^(m-1) mod q
        for (int k = 0; k < m - 1; k++) h = (h * d) % q;

        int p = 0, t = 0;
        for (int k = 0; k < m; k++) {
            p = (d * p + (pattern.charAt(k) - '0')) % q;
            t = (d * t + (text.charAt(k) - '0')) % q;
        }

        System.out.println("h = 10^4 mod 13 = " + h);
        System.out.println("Pattern hash = " + pattern + " mod 13 = " + p);

        for (int s = 0; s <= n - m; s++) {

            String window = text.substring(s, s + m);
            String status = "";

            if (t == p) {
                status = window.equals(pattern) ? "  <- MATCH" : "  <- spurious hit";
            }
            System.out.println("s=" + s + (s < 10 ? " " : "") + " window " + window + " hash " + t + status);

            if (s < n - m) {
                int out = text.charAt(s) - '0';
                int in = text.charAt(s + m) - '0';
                t = (d * (t - out * h) + in) % q;
                if (t < 0) t += q;
            }
        }
    }
}

Output:

h = 10^4 mod 13 = 3
Pattern hash = 31415 mod 13 = 7
s=0  window 23590 hash 8
s=1  window 35902 hash 9
s=2  window 59023 hash 3
s=3  window 90231 hash 11
s=4  window 02314 hash 0
s=5  window 23141 hash 1
s=6  window 31415 hash 7  <- MATCH
s=7  window 14152 hash 8
s=8  window 41526 hash 4
s=9  window 15267 hash 5
s=10 window 52673 hash 10
s=11 window 26739 hash 11
s=12 window 67399 hash 7  <- spurious hit
s=13 window 73992 hash 9
s=14 window 39921 hash 11

Let's check one roll by hand, from s = 6 (hash 7) to s = 7. The digit leaving is 3 and the digit entering is 2:

next = (10 × (7 - 3 × 3) + 2) mod 13
     = (10 × (-2) + 2) mod 13
     = -18 mod 13
     = -18 + 26 = 8              ✓ (and indeed 14152 mod 13 = 8)

Two important lessons from this example:

  • Only 2 of the 15 windows needed a character-by-character check. The other 13 were rejected with a single number comparison.

  • Hash equality is not enough. 67399 mod 13 = 7 too, but 67399 ≠ 31415. Without the verification step, we would report a wrong answer.

Also notice the line if (t < 0) t += q;. In Java, the % operator keeps the sign of the left operand, so -18 % 13 is -5, not 8. Adding q fixes that. Forgetting this is the most common Rabin-Karp bug.


Rabin-Karp in Java

For real text, we use base 256 and a large prime such as 1,000,000,007, so spurious hits become very rare.

import java.util.ArrayList;
import java.util.List;

class Main {

    static final long BASE = 256;              // values in one byte (covers all ASCII chars)
    static final long MOD = 1_000_000_007L;    // a large prime

    static List<Integer> rabinKarp(String text, String pattern) {

        List<Integer> result = new ArrayList<>();
        int n = text.length();
        int m = pattern.length();
        if (m > n) return result;

        // h = BASE^(m-1) % MOD: the weight of the leftmost character
        long h = 1;
        for (int i = 0; i < m - 1; i++) {
            h = (h * BASE) % MOD;
        }

        // Hash of the pattern and of the first window
        long p = 0, t = 0;
        for (int i = 0; i < m; i++) {
            p = (p * BASE + pattern.charAt(i)) % MOD;
            t = (t * BASE + text.charAt(i)) % MOD;
        }

        for (int s = 0; s <= n - m; s++) {

            // Hashes equal → verify character by character
            if (p == t && text.regionMatches(s, pattern, 0, m)) {
                result.add(s);
            }

            // Roll the hash: remove text[s], add text[s + m]
            if (s < n - m) {
                t = (t - text.charAt(s) * h % MOD + MOD) % MOD;  // remove left char
                t = (t * BASE + text.charAt(s + m)) % MOD;       // add right char
            }
        }
        return result;
    }

    public static void main(String[] args) {

        System.out.println(rabinKarp("ABABDABABCABAB", "ABAB"));
        System.out.println(rabinKarp("the cat sat on the mat", "at"));
        System.out.println(rabinKarp("AAAAA", "AA"));
        System.out.println(rabinKarp("HELLO", "XYZ"));
    }
}

Output:

[0, 5, 10]
[5, 9, 20]
[0, 1, 2, 3]
[]

Understanding the Code

  • Why long? The hash is below MOD ≈ 10⁹, and multiplying it by 256 gives about 2.6 × 10¹¹, which overflows an int but fits easily in a long.

  • Why + MOD when removing? Subtracting can make the value negative, and Java's % would then return a negative number. Adding MOD before taking % MOD keeps it in the range 0 to MOD - 1.

  • regionMatches compares m characters of the text starting at s with the pattern, without creating a new substring. This is the verification step.

  • Correctness never depends on the hash. A bad base or a small prime only causes more spurious hits (slower), never a wrong answer, because every hit is verified.

Rabin-Karp Complexity

Case

Time

When

Average / expected

O(n + m)

Few matches and few spurious hits (a good large prime)

Worst

O(n × m)

Many windows need verification: either many real matches (text "AAAA...", pattern "AA...A") or many collisions (a poor modulus)

Extra space

O(1)

Only a few numbers

So why use Rabin-Karp if KMP has a better worst case? Because hashing generalises in ways KMP does not:

  • Many patterns of the same length: put all pattern hashes in a HashSet, roll over the text once, and check each window hash against the set.

  • Comparing substrings quickly: problems like "find the longest substring that appears twice" combine a rolling hash with binary search on the length.

  • 2D matching: the same rolling idea works on rows and columns to find a small image inside a large one.


More Things You Can Do with the LPS Array

The LPS array is useful on its own, not just for searching.

1. Is the String Made of a Repeated Block?

If L = lps[n - 1] is greater than 0 and n is divisible by n - L, the string is a smaller block repeated several times. The block length is n - L.

"abcabcabc": lps = [0, 0, 0, 1, 2, 3, 4, 5, 6]
             n = 9, L = 6, n - L = 3, 9 % 3 == 0  → "abc" repeated 3 times ✓

"abcab":     lps = [0, 0, 0, 1, 2]
             n = 5, L = 2, n - L = 3, 5 % 3 != 0  → not a repetition ✗

2. Search Using Only the LPS Array

Build the LPS array of pattern + "#" + text, where # is a character that appears in neither string. Every position where the LPS value equals m marks the end of a match. The separator stops a border from ever being longer than the pattern.

3. Shortest Palindrome

The LPS value at the end of s + "#" + reverse(s) gives the length of the longest palindromic prefix of s. This solves "Shortest Palindrome" (LeetCode 214) in O(n).


Other Pattern Matching Algorithms

You don't need to code these for most interviews, but you should know they exist:

Algorithm

Idea

Time

Z-Algorithm

Z[i] = length of the longest substring starting at i that matches a prefix of the string. Very similar in spirit to LPS.

O(n + m)

Boyer-Moore

Compares the pattern from right to left and can skip large parts of the text after a mismatch. Very fast on normal text, and used in many text-search tools.

Often much less than n comparisons in practice; O(n × m) worst case for the simple versions

Aho-Corasick

Builds a Trie of many patterns plus KMP-style failure links, then scans the text once.

O(n + total pattern length + number of matches)


Comparing the Algorithms

Property

Naive

KMP

Rabin-Karp

Preprocessing

None

LPS array, O(m)

Pattern hash and d^(m-1), O(m)

Average time

O(n) on typical text

O(n + m)

O(n + m)

Worst time

O(n × m)

O(n + m)

O(n × m)

Extra space

O(1)

O(m)

O(1)

Moves back in the text?

Yes

Never

Only to verify a hit

Many patterns at once

Poor

One pattern at a time

Good (set of hashes, same length)

Main risk

Slow on repetitive text

Tricky to code correctly

Collisions, negative modulo, overflow


Common Mistakes

1. Resetting j to 0 on a mismatch in KMP

Since i never moves back, throwing away the partial match makes KMP miss matches. For example, searching "AAB" in "AAAB" would fail at index 2, restart with j = 0, and never find the match at index 1. On a mismatch with j > 0, use j = lps[j - 1] and do not move i.

2. Using lps[j] instead of lps[j - 1]

j is the number of characters matched so far, so the matched part ends at index j - 1. The border we want is lps[j - 1].

3. Letting the whole string count as its own border

The prefix must be proper. That's why lps[0] = 0 and why the LPS loop starts from i = 1. Starting from i = 0 would compare p[0] with itself and make every value too large.

4. Missing overlapping matches

After a full KMP match, set j = lps[m - 1], not 0. Otherwise, "AA" in "AAAA" gives 2 matches instead of 3.

5. Trusting the hash without verifying

In Rabin-Karp, equal hashes only mean "maybe". Always compare the characters, unless you deliberately accept a tiny chance of error (for example, by using two different hashes in competitive programming).

6. Negative values and overflow in the rolling hash

Add MOD before % after a subtraction, and use long for intermediate products.


Interview Tips and Practice

  • Start by stating the naive O(n × m) approach and its worst case. Then move to KMP or Rabin-Karp.

  • Be able to compute an LPS array by hand. Questions like "find the LPS / failure function of ABABCABAB" are common in written tests.

  • Explain why KMP is linear: the text pointer never moves back, and j can only shrink as much as it has grown.

  • For Rabin-Karp, mention spurious hits and how they are handled. Interviewers often ask, "what happens on a hash collision?"

  • Choose the tool for the problem: one pattern with a guaranteed bound → KMP; many same-length patterns or substring comparisons → rolling hash.

Practice problems:

  • Find the Index of the First Occurrence in a String (LeetCode 28): implement KMP

  • Repeated Substring Pattern (LeetCode 459): LPS trick

  • Shortest Palindrome (LeetCode 214): LPS on s + "#" + reverse(s)

  • Longest Happy Prefix (LeetCode 1392): this is exactly lps[n - 1]

  • Repeated String Match (LeetCode 686)

  • Repeated DNA Sequences (LeetCode 187): rolling hash over windows of length 10

  • Longest Duplicate Substring (LeetCode 1044): rolling hash with binary search


The Main Idea

String pattern matching finds every place where a pattern of length m appears in a text of length n.

Naive       → try every shift, compare characters      → O(n × m) worst
KMP         → precompute LPS, never move back in text  → O(n + m) always
Rabin-Karp  → rolling hash, verify on equal hashes     → O(n + m) average, O(n × m) worst

The two core formulas:

KMP mismatch (j > 0):   j = lps[j - 1]        (i stays)

Rabin-Karp roll:        t = ( d × (t - text[s] × h) + text[s + m] ) mod q
                        where h = d^(m-1) mod q

KMP avoids re-reading the text by remembering how the pattern overlaps with itself. Rabin-Karp avoids comparing strings by comparing numbers, and only checks characters when the numbers agree.

With this chapter, you have covered the full core of DSA for placements: from arrays and complexity analysis, through sorting, linked structures, trees, heaps and graphs, to dynamic programming and string algorithms. The best next step is regular problem practice, using the patterns from these chapters as your toolkit.