String Algorithms

KMP & Z Algorithm

String Matching: KMP & Z Algorithm

The Problem

Given a text T of length n and a pattern P of length m, find all occurrences of P in T.

This is one of the most fundamental problems in computer science -- it appears in text editors, DNA sequence analysis, log searching, compilers, and countless other domains.

Naive Approach -- O(n * m)

The brute-force idea: slide the pattern across the text one position at a time, and at each position compare character by character.

Text:    A A B A A C A A D A A B A A B A
Pattern: A A B A

Position 0: A A B A  vs  A A B A  -->  Match!
Position 1: A B A A  vs  A A B A  -->  Mismatch at index 1 (B != A)
Position 2: B A A C  vs  A A B A  -->  Mismatch at index 0 (B != A)
Position 3: A A C A  vs  A A B A  -->  Mismatch at index 2 (C != B)
Position 4: A C A A  vs  A A B A  -->  Mismatch at index 1 (C != A)
...and so on for every position
CPP
vector<int> naiveSearch(string& text, string& pattern) {
    int n = text.size(), m = pattern.size();
    vector<int> matches;
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && text[i + j] == pattern[j])
            j++;
        if (j == m)
            matches.push_back(i);
    }
    return matches;
}

Worst case: T = "AAAAAAAAAA", P = "AAAB" -- at every position we compare all m characters before finding the mismatch at the end. Total: O(n * m).

The fundamental waste: when a mismatch happens, we throw away everything we learned and start fresh at the next position. But we already know things about the text from the characters we just compared! Can we reuse that information?

Part 1: KMP (Knuth-Morris-Pratt) Algorithm

The Core Insight

When a mismatch occurs after matching some characters, the characters we already matched tell us something about where the next possible match could start. We never need to move backward in the text.

Consider this scenario:

Text:    ... A B C A B C A B D ...
Pattern:     A B C A B D
                       ^
                       mismatch at j=5 (C != D)

We know text[0..4] = "ABCAB" (the part that matched).
Inside "ABCAB", the prefix "AB" equals the suffix "AB".

So we KNOW text[3..4] = "AB" = pattern[0..1].
We can resume matching from j=2 (after the prefix "AB")
without re-examining text[3] and text[4]!

Text:    ... A B C A B C A B D ...
Pattern:         A B C A B D
                     ^
                     resume from j=2

This is the key: the pattern's internal structure tells us exactly where to resume after a mismatch.

The Failure Function (LPS Array)

LPS stands for Longest Proper Prefix which is also a Suffix.

Definition: LPS[i] = length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i].

A "proper" prefix means the prefix cannot be the entire string itself (otherwise LPS[i] would trivially always equal i+1).

Detailed Example: Pattern = "AABAAAB"

Index:    0    1    2    3    4    5    6
Char:     A    A    B    A    A    A    B
LPS:      0    1    0    1    2    2    3

Let's compute each value step by step:

i=0: Substring = "A"
     Proper prefixes: (none -- single char has no proper prefix)
     LPS[0] = 0       (ALWAYS 0 by definition)

i=1: Substring = "AA"
     Proper prefixes:  "A"
     Proper suffixes:  "A"
     "A" == "A"  -->  match of length 1
     LPS[1] = 1

i=2: Substring = "AAB"
     Proper prefixes:  "A", "AA"
     Proper suffixes:  "B", "AB"
     "A"  != "B"
     "AA" != "AB"
     LPS[2] = 0

i=3: Substring = "AABA"
     Proper prefixes:  "A", "AA", "AAB"
     Proper suffixes:  "A", "BA", "ABA"
     "A" == "A"  -->  match of length 1
     "AA" != "BA"
     "AAB" != "ABA"
     LPS[3] = 1

i=4: Substring = "AABAA"
     Proper prefixes:  "A", "AA", "AAB", "AABA"
     Proper suffixes:  "A", "AA", "BAA", "ABAA"
     "A"    == "A"     -->  length 1
     "AA"   == "AA"    -->  length 2  (better!)
     "AAB"  != "BAA"
     "AABA" != "ABAA"
     LPS[4] = 2

i=5: Substring = "AABAAA"
     Proper prefixes:  "A", "AA", "AAB", "AABA", "AABAA"
     Proper suffixes:  "A", "AA", "AAA", "BAAA", "ABAAA"
     "A"     == "A"     -->  length 1
     "AA"    == "AA"    -->  length 2
     "AAB"   != "AAA"
     "AABA"  != "BAAA"
     "AABAA" != "ABAAA"
     LPS[5] = 2

i=6: Substring = "AABAAAB"
     Proper prefixes:  "A", "AA", "AAB", "AABA", "AABAA", "AABAAA"
     Proper suffixes:  "B", "AB", "AAB", "AAAB", "BAAAB", "ABAAAB"
     "AAB" == "AAB"    -->  length 3  (the winner!)
     LPS[6] = 3

Visual Representation of LPS

The LPS value tells you about overlapping structure within the pattern:

Pattern:  A  A  B  A  A  A  B
          |              |
          +--prefix------+
          A  A  B        A  A  B
          [0..2]         [4..6]

When LPS[6] = 3, it means:

  A  A  B  A  A  A  B
  [-----]           |
  prefix of         |
  length 3          |
                    |
  A  A  B  A  A  A  B
                [-----]
                suffix of
                length 3

  The prefix "AAB" equals the suffix "AAB"

Building the LPS Array -- The Clever Part

We could compute LPS naively by checking all prefixes/suffixes for each position, but that would be O(m^2) or O(m^3). Instead, we build it incrementally in O(m) using previously computed values.

The Algorithm

CPP
vector<int> buildLPS(const string& pattern) {
    int m = pattern.size();
    vector<int> lps(m, 0);

    int len = 0;  // length of the previous longest prefix-suffix
    int i = 1;    // lps[0] is always 0, start from 1

    while (i < m) {
        if (pattern[i] == pattern[len]) {
            // Current character extends the match
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                // KEY STEP: fall back to a shorter prefix-suffix
                len = lps[len - 1];
                // DO NOT increment i -- try matching at this new position
            } else {
                // No prefix-suffix possible
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

Why len = lps[len - 1]? (The Hardest Part)

This is the crux of KMP. Let's build deep intuition.

Situation when mismatch occurs:

Pattern:  [ . . . . . . . . . . . . . . . . . ]
           0                                 m-1

At some point during LPS construction, we have:
  - We're at position i
  - len = some value k
  - This means pattern[0..k-1] == pattern[i-k..i-1]  (a match of length k)
  - But pattern[k] != pattern[i]  (mismatch!)

Visually:

Pattern: |  A  B  C  X  Y  A  B  C  Q  A  B  C  X  Y  A  B  C  ...  |
         0  1  2  3  4  5  6  7  8  9  ...

Suppose at position i, len = 5:
  pattern[0..4] = "ABCXY"  matches  pattern[i-5..i-1] = "ABCXY"

  |  A  B  C  X  Y  . . .  A  B  C  X  Y  ?  |
     [0  1  2  3  4]        [i-5 .. i-1]  i
     ^--- prefix ---^       ^--- suffix ---^

  But pattern[5] != pattern[i].

  We want: what is the NEXT longest prefix that equals a suffix of pattern[0..i-1]?

  Key realization: any such prefix-suffix must itself be a prefix-suffix
  of the string pattern[0..4] (= "ABCXY")!

  Why? Because:
  - The new match must be a prefix of pattern (starts at 0)
  - The new match must end at position i-1
  - The new match must be shorter than k=5
  - The new match is contained within both the old prefix AND the old suffix
  - So it must be a prefix AND suffix of pattern[0..k-1]
  - That's exactly lps[k-1]!

  |  A  B  C  X  Y  . . .  A  B  C  X  Y  ?  |
     [0  1  2  3  4]        [i-5 .. i-1]  i

  If lps[4] = 2, it means "AB" is both prefix and suffix of "ABCXY":

  |  A  B  C  X  Y  . . .  A  B  C  X  Y  ?  |
     [0  1]                          [i-2 i-1]  i
     ^-pref^                         ^-suff-^

  So we set len = 2 and check: does pattern[2] == pattern[i]?
  If yes, great! If no, repeat: len = lps[len-1]...

Think of it as a chain of fallbacks:

   len = k
   mismatch --> len = lps[k-1]       (the next best prefix-suffix)
   mismatch --> len = lps[lps[k-1]-1] (the next-next best)
   mismatch --> ... keep going ...
   len = 0 --> give up, lps[i] = 0, move on

Complete Walkthrough: Building LPS for "AABAAB"

Pattern: A  A  B  A  A  B
Index:   0  1  2  3  4  5

Initialize: lps = [0, 0, 0, 0, 0, 0], len = 0, i = 1

--- i=1, len=0 ---
  pattern[1]='A' == pattern[0]='A'?  YES
  len = 1, lps[1] = 1, i = 2
  lps = [0, 1, 0, 0, 0, 0]

--- i=2, len=1 ---
  pattern[2]='B' == pattern[1]='A'?  NO
  len != 0, so len = lps[0] = 0      (fall back)

--- i=2, len=0 ---  (i didn't change!)
  pattern[2]='B' == pattern[0]='A'?  NO
  len == 0, so lps[2] = 0, i = 3
  lps = [0, 1, 0, 0, 0, 0]

--- i=3, len=0 ---
  pattern[3]='A' == pattern[0]='A'?  YES
  len = 1, lps[3] = 1, i = 4
  lps = [0, 1, 0, 1, 0, 0]

--- i=4, len=1 ---
  pattern[4]='A' == pattern[1]='A'?  YES
  len = 2, lps[4] = 2, i = 5
  lps = [0, 1, 0, 1, 2, 0]

--- i=5, len=2 ---
  pattern[5]='B' == pattern[2]='B'?  YES
  len = 3, lps[5] = 3, i = 6
  lps = [0, 1, 0, 1, 2, 3]

Final LPS: [0, 1, 0, 1, 2, 3]

Verification of LPS[5] = 3:

Substring "AABAAB":
  prefix "AAB" == suffix "AAB"  -->  length 3 is correct!

The KMP Search Algorithm

Now we use the LPS array to search efficiently. The idea is identical: when a mismatch occurs, use LPS to skip ahead in the pattern without going back in the text.

CPP
vector<int> kmpSearch(const string& text, const string& pattern) {
    int n = text.size(), m = pattern.size();
    if (m == 0) return {};

    vector<int> lps = buildLPS(pattern);
    vector<int> matches;

    int i = 0;  // index into text (never goes backward)
    int j = 0;  // index into pattern

    while (i < n) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }

        if (j == m) {
            // Full match found at position i - m
            matches.push_back(i - m);
            // Continue searching for more matches
            j = lps[j - 1];
        } else if (i < n && text[i] != pattern[j]) {
            if (j != 0) {
                j = lps[j - 1];  // Skip ahead using LPS
            } else {
                i++;  // No match possible, advance text
            }
        }
    }
    return matches;
}

Complete Visual Walkthrough of KMP Search

Text: "AABAAABAAAB" (n = 11) Pattern: "AAAB" (m = 4) LPS: [0, 1, 2, 0]

LPS computation for "AAAB":
  i=1, len=0: 'A'=='A' -> len=1, lps[1]=1
  i=2, len=1: 'A'=='A' -> len=2, lps[2]=2
  i=3, len=2: 'B'=='A'? NO -> len=lps[1]=1
  i=3, len=1: 'B'=='A'? NO -> len=lps[0]=0
  i=3, len=0: 'B'=='A'? NO -> lps[3]=0
  LPS = [0, 1, 2, 0]

Now the search:

Text:    A  A  B  A  A  A  B  A  A  A  B
Index:   0  1  2  3  4  5  6  7  8  9  10

Step 1:  i=0, j=0   T[0]='A' == P[0]='A'   -> i=1, j=1
Step 2:  i=1, j=1   T[1]='A' == P[1]='A'   -> i=2, j=2
Step 3:  i=2, j=2   T[2]='B' != P[2]='A'   -> j = lps[1] = 1

  Visualization of what just happened:
  Text:    A [A] B  A  A  A  B  A  A  A  B
  Pattern:    [A] A  A  B
              j=1 (we know T[1]='A' = P[0], so resume from j=1)

Step 4:  i=2, j=1   T[2]='B' != P[1]='A'   -> j = lps[0] = 0
Step 5:  i=2, j=0   T[2]='B' != P[0]='A'   -> i=3 (advance text)

Step 6:  i=3, j=0   T[3]='A' == P[0]='A'   -> i=4, j=1
Step 7:  i=4, j=1   T[4]='A' == P[1]='A'   -> i=5, j=2
Step 8:  i=5, j=2   T[5]='A' == P[2]='A'   -> i=6, j=3
Step 9:  i=6, j=3   T[6]='B' == P[3]='B'   -> i=7, j=4

  j == m == 4  -->  MATCH FOUND at position i - m = 7 - 4 = 3
  j = lps[3] = 0

  Text:    A  A  B [A  A  A  B] A  A  A  B
                    ^-----------^
                    Match at position 3

Step 10: i=7, j=0   T[7]='A' == P[0]='A'   -> i=8, j=1
Step 11: i=8, j=1   T[8]='A' == P[1]='A'   -> i=9, j=2
Step 12: i=9, j=2   T[9]='A' == P[2]='A'   -> i=10, j=3
Step 13: i=10, j=3  T[10]='B' == P[3]='B'  -> i=11, j=4

  j == m == 4  -->  MATCH FOUND at position i - m = 11 - 4 = 7
  j = lps[3] = 0

  Text:    A  A  B  A  A  A  B [A  A  A  B]
                                ^-----------^
                                Match at position 7

  i=11 >= n=11  -->  DONE

Result: matches at positions [3, 7]

Notice how i never moved backward. When mismatches happened (steps 3, 4, 5), only j was adjusted. The text pointer marched strictly forward.

Another Walkthrough with Overlapping Matches

Text: "AAAAA" (n = 5) Pattern: "AAA" (m = 3) LPS: [0, 1, 2]

Step 1:  i=0, j=0  'A'=='A' -> i=1, j=1
Step 2:  i=1, j=1  'A'=='A' -> i=2, j=2
Step 3:  i=2, j=2  'A'=='A' -> i=3, j=3

  j == 3 == m  -->  MATCH at position 0
  j = lps[2] = 2    (pattern still has "AA" matched!)

  Text:    [A  A  A] A  A
            0  1  2
  Pattern:  A  A  A

  After fallback, j=2 means pattern[0..1] = "AA" is still matched:
  Text:     A [A  A] A  A
               1  2
  Pattern:    [A  A] A
               0  1

Step 4:  i=3, j=2  'A'=='A' -> i=4, j=3

  j == 3 == m  -->  MATCH at position 1
  j = lps[2] = 2

  Text:    A [A  A  A] A
              1  2  3

Step 5:  i=4, j=2  'A'=='A' -> i=5, j=3

  j == 3 == m  -->  MATCH at position 2
  j = lps[2] = 2

  Text:    A  A [A  A  A]
                 2  3  4

  i=5 >= n=5  -->  DONE

Result: matches at positions [0, 1, 2]

This shows KMP correctly finds overlapping matches, which is a common requirement.

Why KMP is O(n + m)

LPS construction -- O(m):

  • The variable i starts at 1 and only increases (incremented in two of the three branches). It goes up to m-1. So i increases at most m-1 times.
  • Each time len decreases (the len = lps[len-1] branch), i does NOT increase. But len can only decrease as many times as it has previously increased. Since len increases at most m-1 times total (once per i increment), the total number of decreases is also at most m-1.
  • Total operations: at most 2(m-1) = O(m).

Search -- O(n):

  • i starts at 0 and only increases, up to n-1. So i increases at most n times.
  • Each time j decreases (the j = lps[j-1] fallback), i does NOT increase. But j can only decrease as many times as it has previously increased. Since j increases at most n times (once per i increment), the total fallbacks are at most n.
  • Total operations: at most 2n = O(n).

Overall: O(n + m) time, O(m) space (for the LPS array).

The KMP Automaton Perspective

There's an elegant way to think about KMP: it builds a finite automaton for the pattern.

Pattern: "ABABC"
LPS:     [0, 0, 1, 2, 0]

State diagram (each state = number of characters matched):

         A         B         A         B         C
  (0) -------> (1) -----> (2) -----> (3) -----> (4) -----> (5) [ACCEPT]
   ^    |        |          |          |          |
   |    B,C      A,C        B          A,C        A
   |    |        |          |          |          |
   +----+        +-->(0)    +-->(1)    +-->(1)    +-->(1) [because lps[4-1]=lps[3]=2,
                                                            then check P[2]='A'...
                                                            follow the chain]

Every state transition is determined by the LPS array. On a match, go to the next state. On a mismatch at state j, go to state lps[j-1] and try again (exactly what the algorithm does).

Part 2: Z Algorithm

The Z Array -- Definition

For a string S of length n:

Z[i] = length of the longest substring starting at position i that matches a prefix of S.

In other words: Z[i] = the largest k such that S[0..k-1] == S[i..i+k-1].

By convention, Z[0] is undefined (or set to n or 0, since the whole string trivially matches itself as a prefix). We typically ignore or set Z[0] = 0.

Detailed Example

String S = "aabxaab"
Indices:    0123456

Z[0] = (undefined, set to 0)

Z[1] = ?
  Compare S starting at 1 with S starting at 0:
  S[1..] = "abxaab"
  S[0..] = "aabxaab"
  S[1]='a' == S[0]='a'  --> match
  S[2]='b' == S[1]='a'  --> no match
  Z[1] = 1

Z[2] = ?
  S[2..] = "bxaab"
  S[0..] = "aabxaab"
  S[2]='b' != S[0]='a'  --> no match immediately
  Z[2] = 0

Z[3] = ?
  S[3..] = "xaab"
  S[0..] = "aabxaab"
  S[3]='x' != S[0]='a'  --> no match
  Z[3] = 0

Z[4] = ?
  S[4..] = "aab"
  S[0..] = "aabxaab"
  S[4]='a' == S[0]='a'  --> match
  S[5]='a' == S[1]='a'  --> match
  S[6]='b' == S[2]='b'  --> match
  End of string!
  Z[4] = 3

Z[5] = ?
  S[5..] = "ab"
  S[0..] = "aabxaab"
  S[5]='a' == S[0]='a'  --> match
  S[6]='b' == S[1]='a'  --> no match
  Z[5] = 1

Z[6] = ?
  S[6..] = "b"
  S[0..] = "aabxaab"
  S[6]='b' != S[0]='a'  --> no match
  Z[6] = 0

Result: Z = [-, 1, 0, 0, 3, 1, 0]

Visual representation:

Index:   0  1  2  3  4  5  6
String:  a  a  b  x  a  a  b
Z:       -  1  0  0  3  1  0

Z[4]=3 means S[4..6] = "aab" matches prefix S[0..2] = "aab"

String:  a  a  b  x  a  a  b
         [-----]
         prefix of
         length 3
                     [-----]
                     matches prefix!
                     Z[4] = 3

Building the Z Array Efficiently -- The Z-Box

The naive approach (compare from each position) is O(n^2). The Z algorithm achieves O(n) using the Z-box technique.

The Z-box [L, R]: We maintain the interval [L, R] where R is the rightmost position that has been matched as part of some Z[k] computation (i.e., S[L..R] is a copy of S[0..R-L], and R is as far right as possible among all previously computed Z values).

The Three Cases

When computing Z[i]:

Case 1: i > R (we're outside the Z-box)

String:  . . . . . . [L . . . . . R] . . i . . . .
                      ^---Z-box----^      ^
                                          outside!

No information to reuse. Compare character by character:
  S[i] vs S[0], S[i+1] vs S[1], ...
If we match k characters, Z[i] = k, and update [L, R] = [i, i+k-1].

Case 2: i <= R and Z[i - L] < R - i + 1 (the copied Z value fits inside the Z-box)

String:  . . [L . . . . . i . . . . R] . . . .
              ^-------Z-box-----------^
                           ^---remaining-^
                           R-i+1 chars remain in Z-box

We know S[L..R] == S[0..R-L].
So S[i..R] == S[i-L..R-L].
Therefore Z[i] >= Z[i-L].

If Z[i-L] < R-i+1:
  The match at position i-L ended BEFORE hitting the boundary.
  So the match at position i also ends at the same relative place.
  Z[i] = Z[i-L].  No further comparison needed!

Illustration:
  S[0..R-L]:    . . . . [i-L . . . . .] . . R-L . .
                         ^-Z[i-L]-^
                         matches prefix, but stops here

  S[L..R]:      . . . . [i   . . . . .] . . R . . .
                         ^-Z[i]-^
                         same length! Z[i] = Z[i-L]

Case 3: i <= R and Z[i - L] >= R - i + 1 (the copied Z value reaches or exceeds the Z-box boundary)

String:  . . [L . . . . . i . . . . R] ? ? ? . .
              ^-------Z-box-----------^
                           ^-remaining-^
                           R-i+1 chars

Z[i-L] >= R-i+1 means the match at i-L extended AT LEAST to the boundary.
We know S[i..R] matches prefix, but what about beyond R?
We must compare S[R+1] vs S[R-i+1], S[R+2] vs S[R-i+2], etc.
Start extending from R+1 onward.

After extending, update [L, R] = [i, new_R].

Why This is O(n)

The key observation: R only moves to the right. Every character comparison either:

  1. Results in a mismatch (stops, no more work), or
  2. Results in a match and advances R to the right

Since R starts at 0 and ends at most at n-1, the total number of character comparisons that result in matches is at most n. The number of comparisons that result in mismatches is also at most n (one per position). Total: O(n).

Implementation

CPP
vector<int> zFunction(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;  // Z-box [l, r), using half-open interval
                         // r = rightmost matched position + 1

    for (int i = 1; i < n; i++) {
        // Step 1: Initialize z[i] from existing information
        if (i < r) {
            z[i] = min(r - i, z[i - l]);
        }

        // Step 2: Try to extend the match beyond what we know
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }

        // Step 3: Update the Z-box if we went further right
        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}

Note: in this implementation, r is used as a half-open boundary (r = R + 1 from the explanation above). When i < r, we're inside the Z-box. This is a common convention that simplifies the code.

Complete Walkthrough: Z Array for "aabxaabxaab"

String:  a  a  b  x  a  a  b  x  a  a  b
Index:   0  1  2  3  4  5  6  7  8  9  10

Initialize: z = [0,0,0,0,0,0,0,0,0,0,0], l=0, r=0

--- i=1 ---
  i=1 >= r=0, so no initial info.
  Compare: s[0]='a' vs s[1]='a' -> match, z[1]=1
  Compare: s[1]='a' vs s[2]='b' -> mismatch, stop.
  z[1] = 1. Update: l=1, r=2  (Z-box = [1, 2))
  z = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

--- i=2 ---
  i=2 >= r=2, so no initial info.
  Compare: s[0]='a' vs s[2]='b' -> mismatch immediately.
  z[2] = 0. No update (2+0 = 2, not > r=2).
  z = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

--- i=3 ---
  i=3 >= r=2, so no initial info.
  Compare: s[0]='a' vs s[3]='x' -> mismatch.
  z[3] = 0. No update.
  z = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

--- i=4 ---
  i=4 >= r=2, so no initial info.
  Compare: s[0]='a' vs s[4]='a' -> match, z[4]=1
  Compare: s[1]='a' vs s[5]='a' -> match, z[4]=2
  Compare: s[2]='b' vs s[6]='b' -> match, z[4]=3
  Compare: s[3]='x' vs s[7]='x' -> match, z[4]=4
  Compare: s[4]='a' vs s[8]='a' -> match, z[4]=5
  Compare: s[5]='a' vs s[9]='a' -> match, z[4]=6
  Compare: s[6]='b' vs s[10]='b' -> match, z[4]=7
  i+z[4] = 4+7 = 11 = n, stop.
  z[4] = 7. Update: l=4, r=11.

  The Z-box now covers [4, 11):
  String:  a  a  b  x  a  a  b  x  a  a  b
                     [L=4 .................. R=10]
  We know s[4..10] = s[0..6] = "aabxaab"

  z = [0, 1, 0, 0, 7, 0, 0, 0, 0, 0, 0]

--- i=5 ---
  i=5 < r=11, so we're INSIDE the Z-box!
  z[5] = min(r - i, z[i - l]) = min(11-5, z[5-4]) = min(6, z[1]) = min(6, 1) = 1

  Why? Because s[5..10] corresponds to s[1..6] (shifted by l=4).
  z[1] = 1, and 1 < 6 (remaining space in Z-box).
  So Case 2: z[5] = 1. No extension needed.

  Verify: no update to Z-box (5+1=6 < r=11).
  z = [0, 1, 0, 0, 7, 1, 0, 0, 0, 0, 0]

--- i=6 ---
  i=6 < r=11.
  z[6] = min(r-i, z[i-l]) = min(11-6, z[6-4]) = min(5, z[2]) = min(5, 0) = 0
  No extension (s[0]='a' vs s[6]='b' -> mismatch).
  z = [0, 1, 0, 0, 7, 1, 0, 0, 0, 0, 0]

--- i=7 ---
  i=7 < r=11.
  z[7] = min(r-i, z[i-l]) = min(11-7, z[7-4]) = min(4, z[3]) = min(4, 0) = 0
  No extension (s[0]='a' vs s[7]='x' -> mismatch).
  z = [0, 1, 0, 0, 7, 1, 0, 0, 0, 0, 0]

--- i=8 ---
  i=8 < r=11.
  z[8] = min(r-i, z[i-l]) = min(11-8, z[8-4]) = min(3, z[4]) = min(3, 7) = 3

  This is Case 3! z[i-l] = z[4] = 7 >= r-i = 3.
  We know s[8..10] matches s[0..2], but what about beyond position 10?
  i + z[8] = 8 + 3 = 11 = n. No more characters. Can't extend.
  z[8] = 3. No update (8+3=11 = r).
  z = [0, 1, 0, 0, 7, 1, 0, 0, 3, 0, 0]

--- i=9 ---
  i=9 < r=11.
  z[9] = min(r-i, z[i-l]) = min(11-9, z[9-4]) = min(2, z[5]) = min(2, 1) = 1
  Case 2 (1 < 2). z[9] = 1.
  z = [0, 1, 0, 0, 7, 1, 0, 0, 3, 1, 0]

--- i=10 ---
  i=10 < r=11.
  z[10] = min(r-i, z[i-l]) = min(11-10, z[10-4]) = min(1, z[6]) = min(1, 0) = 0
  No extension.
  z = [0, 1, 0, 0, 7, 1, 0, 0, 3, 1, 0]

FINAL Z ARRAY: [0, 1, 0, 0, 7, 1, 0, 0, 3, 1, 0]

Verification:

String:  a a b x a a b x a a b
Z:       - 1 0 0 7 1 0 0 3 1 0

Z[4]=7:  s[4..10] = "aabxaab" == s[0..6] = "aabxaab"  correct!
Z[8]=3:  s[8..10] = "aab"     == s[0..2] = "aab"      correct!
Z[1]=1:  s[1..1]  = "a"       == s[0..0] = "a"        correct!

String Matching with Z Algorithm

The trick: concatenate pattern + "$" + text into a single string, then compute its Z array. The special character $ (which must not appear in either string) prevents matches from crossing the boundary.

Any position i >= m + 1 where Z[i] == m indicates that the text starting at position i - m - 1 matches the pattern.

Pattern = "ab", Text = "xabababy"

Combined = "ab$xabababy"
            0123456789...
            pp$tttttttt    (p = pattern chars, t = text chars)

Z array:   [-, 0, 0, 0, 2, 0, 2, 0, 2, 0, 0]
                          ^      ^      ^
                         Z=2    Z=2    Z=2
                         =m     =m     =m

Positions with Z[i] = 2 (= m):
  i=4:  text position = 4 - 2 - 1 = 1   -> match at T[1]
  i=6:  text position = 6 - 2 - 1 = 3   -> match at T[3]
  i=8:  text position = 8 - 2 - 1 = 5   -> match at T[5]

Verify: "xabababy"
          ^ab          position 1
            ^ab        position 3
              ^ab      position 5  (the 'y' is not part of this)

Wait, let's recheck. T = "xabababy"
Position 1: T[1..2] = "ab" -> match
Position 3: T[3..4] = "ba" -> NOT a match!

Let me recompute. Combined = "ab$xabababy"
                              01234567890

s[4] = 'a', check vs s[0]='a' -> match
s[5] = 'b', check vs s[1]='b' -> match
s[6] = 'a', check vs s[2]='$' -> mismatch
Z[4] = 2 -> text position = 4 - 3 = 1 -> T[1..2] = "ab" YES!

s[6] = 'a', check vs s[0]='a' -> match
s[7] = 'b', check vs s[1]='b' -> match
s[8] = 'a', check vs s[2]='$' -> mismatch
Z[6] = 2 -> text position = 6 - 3 = 3 -> T[3..4] = "ab" YES!

s[8] = 'a', check vs s[0]='a' -> match
s[9] = 'b', check vs s[1]='b' -> match
s[10]= 'y', check vs s[2]='$' -> mismatch
Z[8] = 2 -> text position = 8 - 3 = 5 -> T[5..6] = "ab" YES!

So matches at text positions: 1, 3, 5.
CPP
vector<int> zSearch(const string& text, const string& pattern) {
    string combined = pattern + "$" + text;
    vector<int> z = zFunction(combined);
    vector<int> matches;
    int m = pattern.size();

    for (int i = m + 1; i < (int)combined.size(); i++) {
        if (z[i] == m) {
            matches.push_back(i - m - 1);  // position in original text
        }
    }
    return matches;
}

Why the $ separator? Without it, a Z value could extend from the text portion into the pattern portion, giving a Z value larger than m or giving a false match that spans the boundary. The $ acts as a firewall: since it doesn't appear in either string, no match can cross it. Z values in the text region are capped at m.

Complexity of Z-based String Matching

  • Building the combined string: O(n + m)
  • Computing Z array: O(n + m)
  • Scanning for matches: O(n + m)
  • Total: O(n + m) time, O(n + m) space

KMP vs Z Algorithm -- Detailed Comparison

Aspect KMP Z Algorithm Core data structure LPS (failure) array Z array Preprocessing O(m) time, O(m) space O(n+m) time & space Search O(n) time O(n+m) time (combined) Total time O(n + m) O(n + m) Space O(m) for LPS O(n + m) for combined Z array Online processing YES — can process text character by character NO — needs entire string upfront Conceptual model "Fall back" along pattern on mismatch "Reuse known prefix matches" Ease of impl. Moderate (fallback logic is tricky) Clean and elegant (one simple loop)

When to use which:

  • KMP when you need online/streaming matching (characters arrive one at a time)
  • Z Algorithm when you have the full string and want clean, easy-to-implement code
  • In competitive programming, Z is often preferred for its simplicity
  • For interviews, knowing both is valuable; KMP is asked more often

Applications Beyond Pattern Matching

1. Minimum Period of a String

The period of a string is the smallest p such that S[i] = S[i + p] for all valid i. Equivalently, the string is made up of repetitions of S[0..p-1] (possibly with a partial copy at the end).

Using LPS: period = n - LPS[n-1]

Example: S = "abcabcabc" (n = 9)

LPS for "abcabcabc":
  [0, 0, 0, 1, 2, 3, 4, 5, 6]

period = 9 - LPS[8] = 9 - 6 = 3

Check: "abc" repeated 3 times = "abcabcabc"  Correct!

Why does this work?

S = a b c a b c a b c
    [0 1 2 3 4 5 6 7 8]

LPS[8] = 6 means S[0..5] = S[3..8]:
    a b c a b c a b c
    [0 1 2 3 4 5]          <- prefix of length 6
              [3 4 5 6 7 8] <- suffix of length 6

The "shift" between them is 9 - 6 = 3.
This shift IS the period: every character equals the one 3 positions back.

Full period (string compression): If n % period == 0, the string is a perfect repetition of its period.

CPP
int minPeriod(const string& s) {
    vector<int> lps = buildLPS(s);
    int n = s.size();
    int period = n - lps[n - 1];
    return period;
}

bool isPerfectRepetition(const string& s) {
    int period = minPeriod(s);
    return s.size() % period == 0;
}

2. Count Occurrences of Each Prefix

Problem: For each prefix of length k (1 <= k <= n), how many times does it occur in the string?

Using Z array:

If Z[i] = v, then the prefixes of lengths 1, 2, ..., v all have an occurrence starting at position i.

But iterating over all these lengths for each i would be O(n^2). Instead, we use a counting trick:

CPP
// Count how many times each prefix occurs in the string
vector<int> countPrefixOccurrences(const string& s) {
    int n = s.size();
    vector<int> z = zFunction(s);
    vector<int> cnt(n + 1, 0);  // cnt[k] = # occurrences of prefix of length k

    // Each Z[i] = v means prefix of length v occurs.
    // Instead of incrementing cnt[1], cnt[2], ..., cnt[v],
    // we increment cnt[v] and later do a suffix sum.
    for (int i = 1; i < n; i++) {
        if (z[i] > 0) cnt[z[i]]++;
    }

    // Propagate: if prefix of length k occurs, so does prefix of length k-1
    // (a suffix sum from right to left)
    for (int k = n - 1; k >= 1; k--) {
        cnt[k] += cnt[k + 1];
    }

    // Add 1 for the prefix itself (it always occurs at position 0)
    for (int k = 1; k <= n; k++) {
        cnt[k]++;
    }

    return cnt;  // cnt[k] = number of times prefix of length k appears
}

3. String Compression (Repeated Substring Pattern)

Problem: Given a string S, determine if it can be written as a repetition of a shorter substring.

"abcabc"    -> YES ("abc" x 2)
"abcabcabc" -> YES ("abc" x 3)
"abcab"     -> NO
"aaaa"      -> YES ("a" x 4, or "aa" x 2)

Using LPS:

CPP
bool isRepeated(const string& s) {
    int n = s.size();
    vector<int> lps = buildLPS(s);
    int period = n - lps[n - 1];
    return lps[n - 1] > 0 && n % period == 0;
}

Using Z array:

CPP
bool isRepeated(const string& s) {
    int n = s.size();
    vector<int> z = zFunction(s);
    for (int p = 1; p < n; p++) {
        // Check if p is a valid period
        if (n % p == 0 && z[p] == n - p) {
            return true;  // p is the period
        }
    }
    return false;
}

4. Number of Distinct Substrings

Problem: Count the number of distinct substrings of a string.

Approach with Z (incremental): Add characters one at a time. When we append character c to string t (forming t + c), how many NEW substrings are introduced?

The new substrings are all suffixes of t + c. A suffix is "new" if it hasn't appeared as a substring before. Using the Z array of reverse(t + c), we can find the longest suffix of t + c that appeared in t, and thus count new substrings.

CPP
int countDistinctSubstrings(const string& s) {
    int n = s.size();
    int count = 0;
    string current = "";

    for (int i = 0; i < n; i++) {
        current += s[i];
        // Reverse and compute Z
        string rev = string(current.rbegin(), current.rend());
        vector<int> z = zFunction(rev);

        // Max Z value (excluding z[0]) tells us the longest suffix of current
        // that also appears elsewhere in current
        int maxZ = 0;
        for (int j = 1; j < (int)z.size(); j++) {
            maxZ = max(maxZ, z[j]);
        }

        // New substrings = (length of current) - maxZ
        count += (int)current.size() - maxZ;
    }
    return count;
}

This runs in O(n^2) total which is acceptable for moderate n. For O(n log n) or O(n), use suffix arrays.

5. Shortest Palindrome (LeetCode 214)

Problem: Given a string s, find the shortest palindrome you can form by adding characters to the front.

Key insight: We need to find the longest palindromic prefix of s. Then prepend the reverse of the remaining suffix.

KMP trick: Let rev = reverse(s). Compute s + "$" + rev and build its LPS array. The last LPS value gives the length of the longest prefix of s that matches a suffix of rev -- which is exactly the longest palindromic prefix!

s = "aacecaaa"
rev = "aaacecaa"
combined = "aacecaaa$aaacecaa"
LPS of combined: [0,1,0,0,0,1,2,2,0,1,2,2,3,4,5,6,7]
                                                    ^
LPS[last] = 7

Longest palindromic prefix = s[0..6] = "aacecaa" (length 7)
Remaining: s[7] = "a"
Answer: reverse("a") + s = "a" + "aacecaaa" = "aaacecaaa"

Wait, that's not right. Let me recheck.

s = "aacecaaa", length 8
Longest palindromic prefix has length 7: "aacecaa" IS a palindrome?
  "aacecaa" reversed = "aacecaa" -> YES!
Remaining suffix: "a" (the last character)
Prepend reverse of remaining: "a" + "aacecaaa" = "aaacecaaa"

But wait: "aaacecaaa" reversed = "aaacecaaa" -> it IS a palindrome!
Actually no: reversed = "aaacecaaa" -> same! So yes, it's correct.
CPP
string shortestPalindrome(string s) {
    if (s.empty()) return s;
    string rev = string(s.rbegin(), s.rend());
    string combined = s + "$" + rev;

    vector<int> lps = buildLPS(combined);

    int longestPalPrefix = lps.back();
    string suffix = s.substr(longestPalPrefix);
    string prepend = string(suffix.rbegin(), suffix.rend());
    return prepend + s;
}

Time: O(n), Space: O(n)

Classic LeetCode Problems

Problem 1: Find the Index of the First Occurrence (LC 28)

Problem: Given haystack and needle, return the index of the first occurrence of needle in haystack, or -1.

CPP
// KMP approach
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) return 0;

        // Build LPS
        vector<int> lps(m, 0);
        int len = 0, i = 1;
        while (i < m) {
            if (needle[i] == needle[len]) {
                lps[i++] = ++len;
            } else if (len) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }

        // Search
        i = 0;
        int j = 0;
        while (i < n) {
            if (haystack[i] == needle[j]) {
                i++; j++;
                if (j == m) return i - m;
            } else if (j) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
        return -1;
    }
};
CPP
// Z Algorithm approach
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty()) return 0;
        string combined = needle + "$" + haystack;
        int n = combined.size(), m = needle.size();
        vector<int> z(n, 0);
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i < r) z[i] = min(r - i, z[i - l]);
            while (i + z[i] < n && combined[z[i]] == combined[i + z[i]]) z[i]++;
            if (i + z[i] > r) { l = i; r = i + z[i]; }
            if (z[i] == m) return i - m - 1;
        }
        return -1;
    }
};

Problem 2: Repeated Substring Pattern (LC 459)

Problem: Given string s, check if it can be constructed by taking a substring and appending multiple copies of it.

Intuition: If s has a period p that divides n, then s is composed of n/p copies of s[0..p-1].

CPP
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        // Build LPS
        vector<int> lps(n, 0);
        int len = 0, i = 1;
        while (i < n) {
            if (s[i] == s[len]) {
                lps[i++] = ++len;
            } else if (len) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }

        int lpsLast = lps[n - 1];
        int period = n - lpsLast;
        // Must have lpsLast > 0 (otherwise no repetition)
        // and n must be divisible by the period
        return lpsLast > 0 && n % period == 0;
    }
};

Alternative elegant trick: If s is periodic, then (s + s) contains s as a substring at a position other than 0 and n. So search for s in (s + s)[1..2n-2]:

CPP
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string doubled = s + s;
        // Search in doubled[1..2n-2] (exclude first and last char)
        string sub = doubled.substr(1, doubled.size() - 2);
        return sub.find(s) != string::npos;
        // For O(n) instead of O(n) average with find,
        // use KMP or Z to search.
    }
};

Problem 3: Shortest Palindrome (LC 214)

Already covered above. Here is the full solution:

CPP
class Solution {
public:
    string shortestPalindrome(string s) {
        if (s.size() <= 1) return s;

        string rev(s.rbegin(), s.rend());
        string combined = s + "$" + rev;
        int n = combined.size();

        // Build LPS for combined
        vector<int> lps(n, 0);
        int len = 0, i = 1;
        while (i < n) {
            if (combined[i] == combined[len]) {
                lps[i++] = ++len;
            } else if (len) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }

        // Longest palindromic prefix has length lps[n-1]
        int palLen = lps[n - 1];
        string toAdd = s.substr(palLen);
        reverse(toAdd.begin(), toAdd.end());
        return toAdd + s;
    }
};

Problem 4: Repeated String Match (LC 686)

Problem: Given strings a and b, return the minimum number of times a must be repeated so that b is a substring of the repeated a. Return -1 if impossible.

Intuition: If we repeat a enough times so that the total length >= len(b) + len(a), then if b is ever going to appear, it will appear in that repeated string. We need at least ceil(len(b) / len(a)) copies, and at most one more.

CPP
class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        int minRepeats = (b.size() + a.size() - 1) / a.size();  // ceil division

        string repeated = "";
        for (int i = 0; i < minRepeats; i++) repeated += a;

        // Check with minRepeats copies
        if (zContains(repeated, b)) return minRepeats;

        // Check with one more copy
        repeated += a;
        if (zContains(repeated, b)) return minRepeats + 1;

        return -1;
    }

private:
    bool zContains(const string& text, const string& pattern) {
        string combined = pattern + "$" + text;
        int n = combined.size(), m = pattern.size();
        vector<int> z(n, 0);
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i < r) z[i] = min(r - i, z[i - l]);
            while (i + z[i] < n && combined[z[i]] == combined[i + z[i]]) z[i]++;
            if (i + z[i] > r) { l = i; r = i + z[i]; }
            if (z[i] == m) return true;
        }
        return false;
    }
};

Problem 5: Remove All Occurrences of a Substring (LC 1910)

Problem: Given strings s and part, repeatedly remove the leftmost occurrence of part from s until no occurrences remain.

Note: This problem actually requires a stack-based simulation because removals can create new occurrences. KMP helps by efficiently matching as we build the result character by character.

CPP
class Solution {
public:
    string removeOccurrences(string s, string part) {
        int m = part.size();

        // Build LPS for the pattern
        vector<int> lps(m, 0);
        int len = 0, idx = 1;
        while (idx < m) {
            if (part[idx] == part[len]) {
                lps[idx++] = ++len;
            } else if (len) {
                len = lps[len - 1];
            } else {
                lps[idx++] = 0;
            }
        }

        // Use a stack-like approach: build result char by char,
        // maintaining the KMP state for each position in the result
        string result;
        vector<int> state;  // KMP state (j value) at each position in result
        state.push_back(0);

        for (char c : s) {
            result += c;
            int j = state.back();

            // Advance KMP
            while (j > 0 && c != part[j]) j = lps[j - 1];
            if (c == part[j]) j++;
            state.push_back(j);

            // Full match found -- remove last m characters
            if (j == m) {
                result.erase(result.size() - m, m);
                state.erase(state.end() - m, state.end());
            }
        }

        return result;
    }
};

How this works: We maintain the KMP matching state at each position in the result string. When a full match is detected, we erase the matched portion and restore the KMP state to where it was before those characters were added. This correctly handles cascading deletions.

Advanced Applications

KMP for Counting Matches in a Stream

KMP naturally supports online/streaming input. This is useful when text arrives character by character (network stream, file reading, etc.):

CPP
class KMPMatcher {
    string pattern;
    vector<int> lps;
    int j;  // current state

public:
    KMPMatcher(const string& pat) : pattern(pat), j(0) {
        int m = pat.size();
        lps.resize(m, 0);
        int len = 0, i = 1;
        while (i < m) {
            if (pat[i] == pat[len]) {
                lps[i++] = ++len;
            } else if (len) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
    }

    // Feed one character. Returns true if a full match just completed.
    bool feed(char c) {
        while (j > 0 && c != pattern[j])
            j = lps[j - 1];
        if (c == pattern[j])
            j++;
        if (j == (int)pattern.size()) {
            j = lps[j - 1];
            return true;  // match!
        }
        return false;
    }
};

Finding All Periods of a String

A string can have multiple periods. Using the LPS array, we can find all of them:

CPP
vector<int> allPeriods(const string& s) {
    int n = s.size();
    vector<int> lps = buildLPS(s);
    vector<int> periods;

    // Follow the chain of LPS values from the last position
    int len = lps[n - 1];
    while (len > 0) {
        int period = n - len;
        if (n % period == 0) {  // only if it divides evenly
            periods.push_back(period);
        }
        len = lps[len - 1];
    }
    periods.push_back(n);  // n is always a (trivial) period

    // periods are in increasing order
    return periods;
}

Using Z Array for Longest Common Prefix Queries

Given a string, the Z array directly answers: "What is the longest common prefix between the full string and the substring starting at position i?" This is Z[i] by definition.

This is useful in suffix array construction and various string algorithms.

Summary of Key Formulas

Task Formula / Method Pattern matching KMP: O(n+m) time, O(m) space Z: O(n+m) time, O(n+m) space Minimum period n - LPS[n-1] Is string periodic? LPS[n-1] > 0 && n % period == 0 Longest palindromic prefix LPS of (s + "$" + reverse(s)) last LPS value # occurrences of each prefix Z array + suffix sum trick Online/streaming matching KMP (maintains state with j)

Other String Algorithms (Brief Overview)

Rabin-Karp (Rolling Hash)

Uses a polynomial hash function to compute hashes of all substrings of length m in O(n) time. Compare hash of pattern with each substring hash. On hash match, verify character by character.

  • Average: O(n + m)
  • Worst case: O(nm) (many hash collisions)
  • Advantage: Easy to extend to multi-pattern search and 2D pattern matching

Aho-Corasick

Extension of KMP to multiple patterns simultaneously. Builds a trie of all patterns, then adds failure links (analogous to KMP's failure function) to create an automaton. Processes text in one pass.

  • Time: O(n + m1 + m2 + ... + mk + number_of_matches)
  • Use case: Finding multiple patterns in one text (e.g., banned word filtering)

Suffix Array + LCP Array

A suffix array is a sorted array of all suffixes of a string. Combined with the LCP (Longest Common Prefix) array, it enables efficient solutions to many string problems:

  • All occurrences of a pattern: O(m log n) binary search
  • Longest repeated substring: max LCP value
  • Number of distinct substrings: n(n+1)/2 - sum(LCP[i])
  • Construction: O(n log n) or O(n) with SA-IS algorithm

Suffix Tree

A compressed trie of all suffixes. Extremely powerful but complex to implement (Ukkonen's algorithm builds it in O(n)). Can solve almost any string problem efficiently, but suffix arrays are usually preferred in practice for their simpler implementation and better cache performance.

Templates for Quick Reference

KMP (Compact)

CPP
// Build LPS array for pattern
vector<int> lps(m, 0);
for (int i = 1, len = 0; i < m; ) {
    if (p[i] == p[len]) lps[i++] = ++len;
    else if (len) len = lps[len - 1];
    else lps[i++] = 0;
}

// Search in text
for (int i = 0, j = 0; i < n; ) {
    if (t[i] == p[j]) { i++; j++; }
    if (j == m) { /* match at i-m */ j = lps[j-1]; }
    else if (i < n && t[i] != p[j]) {
        if (j) j = lps[j-1]; else i++;
    }
}

Z Function (Compact)

CPP
vector<int> z(n, 0);
for (int i = 1, l = 0, r = 0; i < n; i++) {
    if (i < r) z[i] = min(r - i, z[i - l]);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
    if (i + z[i] > r) { l = i; r = i + z[i]; }
}

Exercises for Practice

  1. Warm-up: Compute the LPS array for "ABACABABC" by hand. Verify with code.
  2. Warm-up: Compute the Z array for "aabaabaa" by hand. Verify with code.
  3. LC 28: Implement strStr() using both KMP and Z. Compare performance.
  4. LC 459: Repeated Substring Pattern -- solve using KMP, Z, and the (s+s) trick.
  5. LC 214: Shortest Palindrome -- understand why the KMP trick works.
  6. LC 686: Repeated String Match -- why do we need at most ceil(|b|/|a|) + 1 copies?
  7. Challenge: Given a string, find the longest substring that appears at least k times. (Use Z array.)
  8. Challenge: Given a string, find all positions where a rotation of the pattern matches. (Hint: search for pattern in text+text, or pattern+pattern in text.)
All DSA Notes