String Pattern Matching

Idea

String pattern matching finds occurrences of a pattern in a text. Classic algorithms: naive (BF), KMP, etc.

String pattern matching demo

This placeholder can be extended with an animation of the matching process of algorithms such as KMP.

  • Aligning the text and the pattern
  • next array jump demo
  • Match / mismatch process

Algorithms

Naive (Brute Force)

  • Align pattern and text, compare sequentially
  • Time O(mn)O(mn), mm text length, nn pattern length

KMP

  • Uses prefix table (next array) to avoid re-checking
  • Time O(m+n)O(m+n)

Scenarios

  • Text editor find/replace
  • DNA sequence analysis
  • Search/retrieval, data mining

Pseudo-code

Naive:

for i = 0 to m-n:
    for j = 0 to n-1:
        if S[i+j] != P[j]:
            break
    if j == n:
        return i // match
return -1

KMP (simplified):

build next array
i = 0, j = 0
while i < m:
    if S[i] == P[j]:
        i++, j++
        if j == n: return i-n // match
    else if j > 0:
        j = next[j-1]
    else:
        i++
return -1

Deriving the next array

The next array is the heart of KMP. When the pattern prefix P[0..j]P[0..j] mismatches at P[j]P[j], the index jj has to fall back to the position next[j]. next[j] is the length of the longest equal prefix-and-suffix of P[0..j−1]P[0..j-1].

Steps to build it

  1. next[0] = -1 — a mismatch on the very first character means the text pointer advances.
  2. Recurse for next[j]: let k = next[j-1]; if P[j-1] == P[k] then next[j] = k+1, otherwise set k = next[k] and keep falling back.

Example: the pattern “abaabc”

j012345
P[j]abaabc
next[j]-100112

Working through it:

  • next[0] = -1
  • j=1: the substring a has no equal prefix and suffix, so next[1] = 0
  • j=2: the substring ab has longest equal prefix and suffix of length 0, so next[2] = 0
  • j=3: the substring aba has longest equal prefix and suffix a, length 1, so next[3] = 1
  • j=4: the substring abaa has longest equal prefix and suffix a, length 1, so next[4] = 1
  • j=5: the substring abaab has longest equal prefix and suffix ab, length 2, so next[5] = 2

Why it works: on a mismatch at P[j], the pattern pointer falls back to next[j] and comparison continues, while the text pointer i never moves backwards. That single asymmetry is what turns the worst case from O(mn)O(mn) into O(m+n)O(m+n).

Implementation

// Build the next array for pattern P of length n.
void GetNext(char P[], int next[], int n) {
    next[0] = -1;
    int i = 0, k = -1;
    while (i < n - 1) {
        if (k == -1 || P[i] == P[k]) {
            i++;
            k++;
            next[i] = k;
        } else {
            k = next[k];  // fall back to a shorter border
        }
    }
}

// KMP search: S is the text (length m), P is the pattern (length n).
int KMP(char S[], char P[], int next[]) {
    int i = 0, j = 0;
    while (i < (int)strlen(S) && j < (int)strlen(P)) {
        if (j == -1 || S[i] == P[j]) {
            i++;
            j++;
        } else {
            j = next[j];  // the pattern falls back, the text does not
        }
    }
    if (j == (int)strlen(P))
        return i - j;   // match: return the start position
    return -1;          // no match
}

The k = next[k] line in GetNext is the same idea as j = next[j] in the search, applied to the pattern itself. Read together, the two routines say: when a comparison fails, do not start over — fall back to the longest border that could still lead to a match.

Complexity

  • Naive: O(mn)O(mn)
  • KMP: O(m+n)O(m+n)

Exercises

Exercise 1

Explain KMP idea and its advantage.

KMPNext ArrayBacktracking

Approach: The next array avoids repeated comparisons.

Steps:

  1. Use the next array to skip the prefix that has already been matched
  2. Time O(m+n)O(m+n)

Answer: The next array keeps the text pointer from backtracking, which improves the efficiency.

Exercise 2

Time complexity of naive vs KMP?

Naive MatchingKMPTime Complexity

Approach: Compare the characters directly.

Steps:

  1. Naive matching O(mn)O(mn)
  2. KMP O(m+n)O(m+n)

Answer: Naive matching is O(mn)O(mn) while KMP is O(m+n)O(m+n).

Past exam

2022·408

How does KMP avoid backtracking the text pointer?

KMPNext ArrayPattern Matching

Approach: Jumping along the next array.

Steps:

  1. The text pointer does not backtrack when a match fails
  2. The pattern pointer jumps according to the next array

Answer: The pattern jumps along the next array, so the text never backtracks.

Found an issue with this content?

Tell us what could be improved.