Simple String Matching Algorithm:
kmp, Boyer-Moore
Presented By:
Hamida Akhter- 2023100000200
Jesun Ahmed- 2023100000253
Lamisa Rahman- 2023100000652
Introduction to String Matching
What is String Matching?
String matching is the process of finding one or more occurrences of a
smaller string, called the pattern, within a larger string, called the text.
Importance of String Matching
Real-life Applications:
* Search Engines: Find matching words or phrases.
* Text Processing: For finding specific keywords.
* Plagiarism Detection: Check for similar text across documents.
* Pattern Recognition in DNA: Identify gene patterns in biology.
String Matching Algorithms
Types of String Matching Algorithms
Naive Approach: Compare each character in the text with the pattern.
Slow for large texts.
KMP (Knuth-Morris-Pratt): Uses a helper table to avoid unnecessary
comparisons.
Boyer-Moore: Skips large parts of the text by using two heuristics (bad
character rule, good suffix rule).
Naive Approach
Given text string with length n and a pattern with length m, the task is to prints
all occurrences of pattern in text.
Note: You may assume that n > m.
Time Complexity
The worst-case time complexity is O(m * n).
Where m is the length of the pattern and n is the length of the text.
Introduction to KMP Algorithm
KMP: The KMP algorithm is a string matching algorithm that
efficiently searches for a pattern (substring) in a text (larger string).
It was developed by Donald Knuth, Vaughan Pratt, and James H.
Morris in 1977.
How KMP Algorithm Works
KMP uses a preprocessing table (LPS array) to skip characters intelligently
when a mismatch occurs.
Main Steps:
[Link] Step – Build LPS (Longest Prefix Suffix) Array
[Link] the pattern, create an array that tells us the length of the longest prefix
that is also a suffix.
[Link] helps us know how many characters to skip when there's a mismatch.
[Link] Step – Search Pattern in Text
[Link] the LPS array to avoid unnecessary comparisons.
Real-Life Applications of KMP
Text editors like VS Code use KMP for “find and replace”.
DNA sequence matching in bioinformatics.
Plagiarism detection tools.
Spam filters to catch repeated phrases.
Command line tools like grep.
Visual Example
Step-by-step matching process
Time Complexity
Preprocessing (LPS): O(m)
Pattern Searching: O(n)
Total: O(n + m)
Where n is the length of the text and m is the length of the pattern.
It’s much faster than the naive method in the worst case.
Introduction to Boyer-Moore Algorithm
Boyer-Moore: The Boyer Moore String Search Algorithm is one of
the most efficient string searching algorithms out there, and is often
the benchmark for string searching algorithms. It was developed in
1977, By Professor Robert Stephen Boyer and J Strother Moore.
Where is Boyer-Moore Used?
The Boyer-Moore algorithm is used in:
Text editors like Notepad++ and VS Code
Search engines
Word processors like Microsoft Word
Linux command grep
Boyer-Moore Working Principle
Boyer-Moore works in two main parts:
Bad Character Rule: If there’s a mismatch, the pattern is shifted
to align the character in the text with the rightmost occurrence of
that character in the pattern.
Good Suffix Rule: If part of the pattern matches, the rest of the
pattern is shifted to try matching it elsewhere.
Bad Character Rule
If we mismatch, use knowledge of the mismatched text character to skip
alignments.
Good Suffix Rule
If we match some characters, use knowledge of the matched characters to skip
alignments.
Time Complexity
Worst Case: O(n × m)
Example Scenario:
• Pattern: “aaaaab”
• Text: “aaaaaaaaaaaaa”
Here, mismatch happens at the end of the pattern every time, but all characters before it
match. So the pattern only moves by 1 position each time.
Result: Algorithm behaves like brute-force → O(n × m)
Conclusion
Algorithm Best For Time Complexity
KMP Repeated patterns O(n + m)
Boyer-Moore Long alphabets Best: sublinear, Worst:
O(n * m)