String Algorithms and Pattern Matching

Naive string matching slides the pattern (length m) over the text (length n) one position at a time, re-comparing from scratch on each mismatch: worst case O(nm). KMP (Knuth-Morris-Pratt) precomputes a failure/LPS (Longest Proper Prefix which is also Suffix) array in O(m), then scans the text once without backtracking, giving O(n + m) total. Memory aid: 'KMP never re-reads a text character.' The LPS array tells how far to shift the pattern on a mismatch by reusing already-matched prefix information. KMP space is O(m) for the LPS array. Rabin-Karp uses hashing for average O(n+m) but worst-case O(nm) due to hash collisions.

The Knuth-Morris-Pratt (KMP) algorithm matches a pattern against a long text in linear time, and its whole speed advantage comes from one tiny pre-computed array — the LPS array, also called the failure function. Mastering how to build LPS in O(m) is the single highest-yield investment for any GATE string-matching question.

Definition: For a pattern P of length m, LPS[i] is the length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i]. "Proper" means the prefix cannot be the entire substring itself.

Definition: A prefix of a string is any substring that starts at index 0; a suffix is any substring that ends at the last index. A border of a string is a substring that is simultaneously a (proper) prefix and a suffix — LPS records the longest border at every position.

Why LPS exists at all

A naïve string match restarts from scratch whenever a mismatch occurs, throwing away the information it has just learned about the pattern. That's why naïve matching runs in O(nm) in the worst case (think pattern "AAAAB" in text "AAAAAAAAAB").

KMP's insight is — if you have matched the first j characters of the pattern against the text and then the (j+1)-th fails, you already know what those first j characters of the text look like (they are exactly P[0..j-1]). So you can ask "what's the longest prefix of the pattern that is also a suffix of the j characters I just matched?" That's LPS[j-1]. By jumping the pattern index back to LPS[j-1] instead of zero, KMP never re-examines a text character — giving you O(n + m) overall.

Building the LPS array for ABABACA

Following the example from the source, pattern = "ABABACA":

• "A" → 0 (a single character has no proper border)
• "AB" → 0 (no character matches the start)
• "ABA" → 1 (prefix "A" equals suffix "A")
• "ABAB" → 2 (prefix "AB" equals suffix "AB")
• "ABABA" → 3 (prefix "ABA" equals suffix "ABA")
• "ABABAC" → 0 (the trailing "C" kills every border — no prefix of the pattern starts with "C")
• "ABABACA" → 1 (only "A" matches as border)

So LPS = [0, 0, 1, 2, 3, 0, 1].

The two-pointer construction

The standard algorithm uses two indices, len (length of the current longest border) and i (current position):

len = 0
LPS[0] = 0
i = 1
while i < m:
    if P[i] == P[len]:
        len = len + 1
        LPS[i] = len
        i = i + 1
    else:
        if len != 0:
            len = LPS[len - 1]   # fall back, do not advance i
        else:
            LPS[i] = 0
            i = i + 1

Even though there is a loop inside a loop, each iteration either advances i or strictly decreases len. Since len cannot fall below zero and i is bounded by m, total work is O(m). This amortised analysis is a favourite GATE pen-and-paper exercise.

Using LPS during the actual match

Now, during text matching, suppose you have matched j characters of the pattern and the next text character does not match P[j]. Instead of restarting at P[0], KMP sets j = LPS[j-1] and tries again with the same text index. The text index never moves backward, which is the whole reason KMP is O(n + m) for a text of length n.

If j = 0 and there is still a mismatch, only then do you advance the text index. This is the second key invariant — the text pointer is monotonically non-decreasing.

Why it matters: KMP, the LPS array, and the closely related Z-array are recurring NAT and MCQ questions in GATE CSE — usually worth 2 marks each and totalling 4 to 6 marks across years. Beyond exams, LPS appears in plagiarism detection, DNA pattern matching, log analysis, and the grep -F family of tools. Understanding LPS gives you a free pass into Z-algorithm, Aho-Corasick, and suffix automaton, which are the basis of many advanced string problems.

Real-world example: Bioinformatics labs at IISc and IIT Delhi use KMP-style matchers to find short motifs (10–30 bp DNA patterns) inside billion-base genomes. A naïve search would take days; KMP brings it down to minutes because the LPS array exploits the heavy repetition that DNA naturally contains — sequences like "ATAT…" or "CGCG…" are exactly the cases where LPS shines.

Common misconception: Students sometimes write that LPS[i] is the longest prefix equal to "any" suffix of the pattern. It must be a suffix of the specific prefix P[0..i], not of the whole pattern. Another frequent error is forgetting the word "proper" — LPS["A"] is 0, not 1, because the only prefix equal to a suffix of "A" is "A" itself, which is not proper.

Question: For pattern "AABAACAABAA", compute the LPS array and use it to count how many times we save work compared to a naïve match.
Solution:
Step 1: Walk through character by character.

• A → 0
• AA → 1 ("A" matches "A")
• AAB → 0 ("B" breaks the border)
• AABA → 1
• AABAA → 2
• AABAAC → 0
• AABAACA → 1
• AABAACAA → 2
• AABAACAAB → 3 ("AAB" prefix = "AAB" suffix)
• AABAACAABA → 4
• AABAACAABAA → 5

Step 2: LPS = [0,1,0,1,2,0,1,2,3,4,5].
Step 3: When matching against a long text, every time KMP falls back from j to LPS[j-1], it skips that many comparisons. For a heavily repetitive pattern like this, the savings are huge.
Conclusion: The LPS array correctly identifies the recurring "AA" and "AAB" borders, letting KMP avoid the O(nm) worst case completely.

Concatenating two strings of lengths a and b: O(a+b). Comparing two strings: O(min length) worst case. Reversing a string: O(n). Checking palindrome: O(n) two-pointer. Naive substring search: O(n*m). KMP / Z-algorithm: O(n+m). Computing all character frequencies: O(n) with a fixed-size count array (O(1) if alphabet size is constant, e.g., 256 ASCII). Sorting characters of a string: O(n log n) comparison sort, or O(n + k) counting sort for fixed alphabet k. Memory aid: 'linear scans for most one-pass tasks, n log n only when sorting by comparison.' In C, string length via strlen is O(n) because it scans to the null terminator.

Cover the answer, recall, then check. 12 cards. n = text length, m = pattern length.

Q1. Naive (brute-force) pattern matching worst-case time?
A1. O(n·m) — e.g. text "aaaa…a", pattern "aaa…ab".

Q2. KMP (Knuth–Morris–Pratt) total time?
A2. O(n + m): O(m) preprocessing + O(n) scan.

Q3. What does KMP preprocess, and in what time?
A3. The failure / prefix function (LPS array) in O(m).

Q4. Definition of LPS[i]?
A4. Length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i].

Q5. Key property that makes KMP linear?
A5. The text pointer never moves backward; on a mismatch the pattern shifts using the LPS array.

Q6. Maximum number of character comparisons KMP makes on the text?
A6. At most 2n.

Q7. Rabin–Karp core technique and average time?
A7. Rolling hash; average O(n + m).

Q8. Rabin–Karp worst-case time and when it occurs?
A8. O(n·m), when many spurious hash hits force full re-checks.

Q9. Boyer–Moore best-case time?
A9. Sublinear, O(n/m) — it skips using the bad-character / good-suffix heuristics; worst case O(n·m) (classic form).

Q10. LPS array of pattern "AABAACAABAA" — what are its entries?
A10. One entry per character: [0,1,0,1,2,0,1,2,3,4,5].

Q11. Longest Common Subsequence (LCS) DP time and space?
A11. O(n·m) time, O(n·m) space (reducible to O(min(n,m)) space).

Q12. Edit (Levenshtein) distance DP time?
A12. O(n·m) time.

Key formulas

• Naive matching: O(n·m) worst (text length n, pattern length m).
• KMP: O(n + m); prefix (failure) function computed in O(m).
• Rabin–Karp: O(n + m) average, O(n·m) worst (hash collisions); rolling hash.
• Boyer–Moore: sublinear on average, O(n·m) worst.
• Z-algorithm and suffix automaton: O(n).
• Number of distinct substrings of a string of length n: up to n(n+1)/2.
• Longest common subsequence (two strings length m,n): DP in O(m·n).
• Edit (Levenshtein) distance: DP in O(m·n).
• Suffix array construction: O(n log n).

Usage: KMP/Z give linear matching; use O(mn) DP for similarity (LCS, edit distance).