DSA: String Algorithms
Master pattern matching, hashing, suffix structures, and palindrome algorithms for strings.
Naive Pattern Matching
Check every position in the text as a potential start of the pattern. Simple to implement but O(n * m) in the worst case (e.g., text = "aaaa...a", pattern = "aab").
Naive Pattern Matching
Slide pattern over text one position at a time; compare all m characters at each position.
- Outer loop: n - m + 1 starting positions
- Inner loop: compare up to m characters
- Worst case: O(n * m), all partial matches before mismatch
- Best case: O(n), mismatch on first character each time
Naive Pattern Matching
C++Slide and compare: O(n*m) worst case, simple baseline implementation.
KMP Algorithm
KMP preprocesses the pattern into an LPS (Longest Proper Prefix which is also Suffix) array. On mismatch, instead of restarting, the LPS array tells how far back to continue matching. Total time: O(n + m).
KMP (Knuth-Morris-Pratt)
LPS[i] = length of longest proper prefix of pat[0..i] that is also a suffix.
- Build LPS in O(m): two pointers len and i
- On mismatch at j: don't reset to 0, set j = lps[j-1]
- On match: advance both text pointer i and pattern pointer j
- Never reprocess a text character: O(n) scan + O(m) preprocessing = O(n + m)
KMP Pattern Search
C++LPS array skips redundant comparisons on mismatch; O(n + m) total.
Rabin-Karp Algorithm
Use a rolling hash to compare the pattern hash against each window hash in the text. A hash match triggers a character-by-character verification (to handle collisions). Average O(n + m).
Rabin-Karp Rolling Hash
Roll the window: subtract outgoing character, add incoming character, multiply by base, all O(1).
- Hash: treat string as base-b number mod a large prime
- Roll: newHash = (oldHash - text[i]*h) * base + text[i+m] (mod prime)
- Hash match: verify character by character to rule out false positives
- Average: O(n + m); worst case O(n*m) if many hash collisions
- Useful for multi-pattern search (Aho-Corasick) and plagiarism detection
Rabin-Karp
C++Rolling hash recomputes window hash in O(1); verify on hash match.
Z Algorithm
Build the Z-array where Z[i] is the length of the longest substring starting at i that matches a prefix of the string. Concatenate pattern + "$" + text, then find positions where Z[i] == m.
Z Algorithm
Z[i] = longest match between s[i..] and s[0..]. Pattern search: look for Z[i] == len(pattern).
- Maintain Z-box [l, r]: the rightmost Z-interval seen so far
- If i is inside Z-box: use previously computed Z value to skip work
- Extend beyond Z-box by brute comparison; update Z-box if extended
- Concatenate: pat + '$' + text; $ ensures Z[i] never exceeds m
- Time: O(n + m), Space: O(n + m)
Z Algorithm Pattern Search
C++Concatenate pattern+'$'+text; positions where Z[i]==m are matches.
Suffix Array
A suffix array stores the starting indices of all suffixes of a string in lexicographic order. Combined with the LCP (Longest Common Prefix) array it supports pattern search, counting distinct substrings, and longest repeated substring in O(n log n) or O(n).
Suffix Array
Sort all suffixes lexicographically; store their starting indices. O(n log n) with sort + comparison.
- Naive build: O(n² log n), sort n strings of avg length n
- O(n log n) build: sort by 2^k length prefixes iteratively (prefix doubling)
- Pattern search: binary search on suffix array in O(m log n)
- LCP array: adjacent suffix array entries' longest common prefix
- Count distinct substrings = n*(n+1)/2 - sum(LCP array)
Suffix Array (Naive Build)
C++Sort all suffixes lexicographically; their start indices form the suffix array.
Manacher's Algorithm
Find the longest palindromic substring in O(n). Transform the string by inserting separators (#) to handle even-length palindromes uniformly, then use the mirror property to avoid redundant expansion.
Manacher's Algorithm
p[i] = palindrome radius at position i in the transformed string. Use mirror and center to skip work.
- Transform: insert '#' between chars and at boundaries → '#a#b#a#'
- p[i]: max r such that t[i-r..i+r] is a palindrome in transformed string
- Mirror trick: if i is inside current rightmost palindrome, p[i] >= p[mirror]
- Expand beyond known boundary; update center and right boundary when extended
- Answer: max p[i]; actual length = p[i], start in original = (i - p[i]) / 2
Manacher's Algorithm
C++Transform string, use mirror property to expand palindromes in O(n).
Smallest Window Containing Pattern
Find the minimum length substring of the text that contains all characters of the pattern (with correct frequencies). Use sliding window with two pointers and a frequency map.
Smallest Window
Expand right until all pattern chars covered; shrink left while still valid; track minimum window.
- need[c]: required frequency of each pattern character
- have: count of pattern characters currently satisfied in the window
- Expand right pointer: if char in pattern and freq matches, increment have
- Shrink left pointer while have == total required; update min window
- Time: O(n + m), Space: O(m) for frequency map
Smallest Window Containing Pattern
C++Sliding window: expand right to cover all chars, shrink left while valid.
String Algorithm Comparison
Pattern matching algorithms trade preprocessing complexity for faster search.
| Algorithm | Preprocessing | Search | Key Idea |
|---|---|---|---|
| Naive | None | O(n * m) | Slide and compare |
| KMP | O(m) LPS array | O(n) | Skip via LPS on mismatch |
| Rabin-Karp | O(m) hash | O(n) avg, O(nm) worst | Rolling hash window |
| Z Algorithm | O(n + m) | O(n + m) | Z-box mirror property |
| Suffix Array | O(n log n) | O(m log n) | Binary search on sorted suffixes |
| Manacher's | O(n) transform | O(n) | Mirror property for palindromes |
| Smallest Window | O(m) freq map | O(n) | Two-pointer sliding window |
Knowledge Check
1. Naive pattern matching worst-case time complexity is:
2. The LPS (Longest Proper Prefix which is also Suffix) array in KMP is used to:
3. Rabin-Karp uses a rolling hash to:
4. Z[i] in the Z-algorithm represents:
5. KMP pattern search runs in:
6. Manacher's algorithm finds the longest palindromic substring in:
7. A suffix array is:
8. Smallest Window Containing Pattern uses which technique?