Text
The larger sequence being searched.
T[0 … n−1]🔤 String Pattern Matching
Find a pattern inside larger text efficiently using direct comparison, prefix preprocessing, rolling hashes and right-to-left character skipping.
LEARNING GOALS
🎯 Learning Objectives
After completing this level, you should be able to:
- Explain text, pattern, alignment, shift and occurrence.
- Implement the Naive and KMP pattern-matching algorithms.
- Construct and interpret the KMP LPS array.
- Explain rolling hashes and hash collisions in Rabin–Karp.
- Apply the Boyer–Moore bad-character heuristic.
- Compare preprocessing, search time and suitable applications.
- Select an appropriate algorithm for repeated, large or multi-pattern searches.
FOUNDATION
🧭 1. What Is Pattern Matching?
Given a text T of length n and a pattern P of length m, pattern matching finds every starting index where P occurs in T.
Example: Text =
ABABA, Pattern = ABA. Matches begin at indices 0 and 2; overlapping occurrences are valid.Pattern
The smaller sequence we want to locate.
P[0 … m−1]Edge cases: Decide how your program handles an empty pattern, a pattern longer than the text, repeated characters, overlaps and case sensitivity.
WHY IT MATTERS
🌍 2. Applications
Search Engines
Locate words, phrases and tokens inside indexed documents.
Bioinformatics
Search DNA and protein sequences for important motifs.
Cybersecurity
Detect signatures and suspicious patterns in network traffic.
Editors
Support Find, Replace and syntax-highlighting operations.
Compilers
Recognize tokens and language constructs during lexical analysis.
Log Analysis
Locate errors, identifiers and event sequences in large logs.
SEARCH MODEL
📘 3. Alignment, Shift and Comparison
Align
Place P below a candidate window of T.
Compare
Test the aligned characters according to the algorithm.
Shift
Move P using one position or information already learned.
Report
Record the starting index after all m characters match.
Possible alignments: when m ≤ n, the pattern can begin at n − m + 1 positions.
DIRECT COMPARISON
🔍 4. Naive Pattern Matching
The Naive method tries every possible shift and compares pattern characters from left to right.
for (shift = 0; shift <= n - m; shift++) {
for (j = 0; j < m; j++)
if (text[shift + j] != pattern[j]) break;
if (j == m) report(shift);
}Strength
No preprocessing and very easy to implement.
Space: O(1)Weakness
It may recheck many characters after each mismatch.
Worst time: O(nm)PREFIX PREPROCESSING
🧩 5. Knuth–Morris–Pratt (KMP)
KMP preprocesses the pattern so a mismatch does not force the text pointer to move backward. It uses the LPS array.
LPS[i] is the length of the longest proper prefix of
P[0…i] that is also a suffix of that substring. “Proper” means the prefix is not the entire substring.| Pattern index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Pattern | A | B | A | B | C | A | B | A | B |
| LPS | 0 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 4 |
Advance both i and j.
Set j = LPS[j−1]; do not move i.
Advance only i.
Report i−j, then continue using LPS[m−1].
KMP complexity: LPS preprocessing O(m) + search O(n) = O(n + m).
ROLLING HASH
#️⃣ 6. Rabin–Karp Algorithm
Rabin–Karp compares a hash of the pattern with the hash of each text window. A rolling hash updates the next window efficiently.
Hash Pattern
Calculate the pattern hash once.
Hash Window
Calculate the first m-character text hash.
Compare Hashes
Different hashes guarantee different strings.
Verify
Equal hashes require character comparison because collisions are possible.
Spurious hit: two different strings may have the same hash. Always verify the characters before reporting a match.
Expected search time is O(n + m) with a good hash, while the worst case is O(nm) when many collisions occur.
RIGHT-TO-LEFT SKIPPING
⏩ 7. Boyer–Moore Method
Boyer–Moore compares the pattern from right to left and can skip several text positions after a mismatch.
Bad-Character Rule
Align the mismatching text character with its last occurrence in the pattern, or move past it if absent.
Uses a last-occurrence tableGood-Suffix Rule
Reuse information about a suffix that already matched before the mismatch.
Allows larger safe shiftsPractical advantage: Boyer–Moore often examines fewer than n text characters for long patterns over large alphabets, although its exact guarantees depend on the implemented heuristics.
ALGORITHM SELECTION
⚖️ 8. Comparison of Methods
| Algorithm | Preprocessing | Typical/Worst Search | Main Idea | Useful When |
|---|---|---|---|---|
| Naive | None | O(nm) worst | Try every alignment | Small inputs and simple code |
| KMP | O(m) | O(n) | LPS prefix fallback | Guaranteed linear single-pattern search |
| Rabin–Karp | O(m) | O(n) expected; O(nm) worst | Rolling hash | Many patterns or plagiarism-style scanning |
| Boyer–Moore | Alphabet + pattern | Often sublinear; variant-dependent worst case | Right-to-left comparisons and skips | Long patterns and large alphabets |
INTERACTIVE ALGORITHM VISUALIZATION
🎬 9. Premium Pattern-Matching Visualizer
CodeBhavya
Enter a text and pattern, choose an algorithm and click Load Visualizer. The animation is created only after the button is pressed.
Choose an example or enter values, then click Load Visualizer.
🔤 Live Alignment
TEXT
PATTERN
Step 0 of 0
C IMPLEMENTATION
💻 10. KMP Pattern Matching in C
#include <stdio.h>
#include <string.h>
void buildLPS(const char pattern[], int m, int lps[]) {
int length = 0, i = 1;
lps[0] = 0;
while (i < m) {
if (pattern[i] == pattern[length])
lps[i++] = ++length;
else if (length != 0)
length = lps[length - 1];
else
lps[i++] = 0;
}
}
void kmpSearch(const char text[], const char pattern[]) {
int n = strlen(text), m = strlen(pattern), lps[m];
buildLPS(pattern, m, lps);
int i = 0, j = 0;
while (i < n) {
if (text[i] == pattern[j]) { i++; j++; }
if (j == m) {
printf("Match at index %d\n", i - j);
j = lps[j - 1];
} else if (i < n && text[i] != pattern[j]) {
if (j != 0) j = lps[j - 1];
else i++;
}
}
}
int main(void) {
char text[200], pattern[100];
scanf("%199s %99s", text, pattern);
kmpSearch(text, pattern);
return 0;
}Sample Input
ABABDABACDABABCABAB
ABABCABABSample Output
Match at index 10C PROGRAM + TRACING
🔍 11. Program Tracing — KMP Search
Trace text = ABABAC, pattern = ABAC and LPS = [0, 0, 1, 0]. Every value change is connected to the highlighted statement.
PROGRAM TRACING — KMP PATTERN SEARCH
💻 C Program
buildLPS(pattern, m, lps);
int i = 0, j = 0;
while (i < n) {
if (text[i] == pattern[j]) {
i++;
j++;
if (j == m) { report(i - j); j = lps[j - 1]; }
else if (i < n && text[i] != pattern[j]) {
if (j != 0) j = lps[j - 1];
else i++;🧠 What is happening?
Press Next to begin the KMP trace.
📊 Live Variables
Text Index i0
Pattern Index j0
Comparisons0
LPS Array
[0, 0, 1, 0]Output
—
Step 0
PERFORMANCE SUMMARY
📈 12. Complexity Analysis
| Algorithm | Best/Expected | Worst | Extra Space |
|---|---|---|---|
| Naive | O(n) | O(nm) | O(1) |
| KMP | O(n + m) | O(n + m) | O(m) |
| Rabin–Karp | O(n + m) expected | O(nm) | O(1) or O(k) |
| Boyer–Moore | Often sublinear | Variant-dependent | O(m + alphabet) |
INTERVIEW FOCUS
💡 13. Important Questions and Decisions
Why does KMP never move i backward?
The LPS array preserves the longest prefix already known to match, so comparison resumes at a safe pattern position.
Why verify equal hashes?
A hash collision can make different strings share the same hash value.
How are overlaps reported?
After a match, continue from the appropriate prefix value instead of resetting blindly.
Which method for many patterns?
Rabin–Karp can compare several pattern hashes; tries or Aho–Corasick are better for large pattern sets.
AVOID THESE ERRORS
⚠️ 14. Common Mistakes
❌ Incorrect LPS meaning
LPS stores a length, not a direct text shift or character index.
❌ Moving both pointers on mismatch
In KMP, i stays fixed when j falls back through LPS.
❌ Reporting a hash as a match
Equal hashes must be verified character by character.
❌ Missing overlaps
Continue with LPS after a full match to discover overlapping occurrences.
CHECK YOUR UNDERSTANDING
✍️ 15. Practice Problems
Solve each question first. Use Hint only when needed and Show Answer to verify your reasoning.
1. How many alignments exist when n = 12 and m = 5?
Use n − m + 1.
8 alignments.
2. Find all occurrences of ABA in ABABA.
Overlapping matches are allowed.
Indices 0 and 2.
3. Give the worst-case time complexity of Naive matching.
Each alignment may compare all m characters.
O(nm).
4. What does LPS stand for?
It connects a proper prefix with a suffix.
Longest Proper Prefix which is also a Suffix.
5. Construct the LPS array for AAAA.
Each additional A extends the previous border.
[0, 1, 2, 3].
6. Construct the LPS array for ABAC.
ABA has border A; ABAC has none.
[0, 0, 1, 0].
7. In KMP, what happens on a mismatch when j > 0?
Do not move i backward.
Set j = LPS[j−1] and keep i unchanged.
8. In KMP, what happens on a mismatch when j = 0?
No shorter matched prefix remains.
Increment i.
9. Why is KMP linear?
Track the forward movement of i and controlled fallback of j.
Neither pointer repeatedly rescans the text; preprocessing is O(m) and searching is O(n), giving O(n + m).
10. What is a rolling hash?
Reuse the previous window hash.
A hash that removes the outgoing character and adds the incoming character to obtain the next window hash efficiently.
11. What is a spurious hit in Rabin–Karp?
Equal hashes do not always mean equal strings.
A hash collision where the window hash equals the pattern hash but the strings differ.
12. Why does Rabin–Karp verify characters after equal hashes?
Think about collisions.
To distinguish a real match from a hash collision.
13. From which direction does Boyer–Moore normally compare?
It starts at the pattern’s last character.
Right to left.
14. What information does the bad-character table store?
Think of the last pattern occurrence.
The last occurrence position of each character in the pattern.
15. Which algorithm gives guaranteed O(n + m) search including preprocessing?
It uses the LPS array.
KMP.
16. Which method is simplest for a tiny one-time input?
Preprocessing may not be worthwhile.
The Naive method is often sufficient.
17. What should KMP do after finding a match if overlaps are required?
Reuse the longest border of the full pattern.
Set j = LPS[m−1] and continue.
18. What is the LPS array for ABCD?
No proper prefix is also a suffix.
[0, 0, 0, 0].
19. If m > n, how many valid pattern alignments exist?
The pattern cannot fit inside the text.
Zero.
20. Choose a suitable method for searching many patterns by hash inside one document.
One window hash can be compared with multiple pattern hashes.
Rabin–Karp is suitable; for very large pattern sets, also consider Aho–Corasick.
QUICK RECALL
📝 16. Quick Revision
- Pattern matching finds every valid starting index of P in T.
- Naive matching tries all n−m+1 alignments.
- KMP uses LPS and never moves the text pointer backward.
- LPS describes reusable prefix–suffix structure inside the pattern.
- Rabin–Karp uses rolling hashes but verifies equal-hash windows.
- Boyer–Moore compares from right to left and makes larger safe shifts.
- Overlapping matches require continuing from a valid prefix state.
- Choose the algorithm according to guarantees, alphabet, pattern count and input size.