String matching algorithm

• The problem states that we are given a text string (let's say text) having the length n and a
pattern string (let's say pattern) having the length m
• We need to write a function that takes these two strings (pattern, and text) and prints all the
occurrences of the pattern string in the text string
• We can assume that the value of m will always be less than the value of n.
• We can assume 0-based indexing.
Example:
Cont’d
Cont’d
STRING:
• A string is an immutable data type that is used to store the sequence of characters
• Strings are one of the most widely used data types of any programming language
• A string can be easily created using quotes (either single quotes or double quotes)
Naive string matching algorithm:
• In the example above, the input string is "Hello World! and the pattern that needs to be
searched is "World!“
• We can see that the size of the pattern is 6 (i.e. m) and the size of the input text is 12 (i.e. n)
• We can start searching for the pattern in the input text by sliding the pattern over the text one
by one and checking for a match.
• So, we would start searching from the first index and slowly move our pattern window from
index-0 to index-6
• At index-6, we can see that both the W's are matching. So, we will search the entire pattern
in the window starting with index-6.
Cont’d
• Hence, we will find a match and return the starting index of the pattern as the answer
• For better clarity of the window search, please refer to the image provided below
Cont’d
Naive Pattern Searching
• One approach to search a certain pattern in the input string can be using two loops (nested
loops)
• We will use all the possible placements of the pattern string in the input text and check
whether the current positioning matches the input pattern or not
• If the current positioning matches with the input pattern then we would return the first index
of the matching window (of input text)
• If all the possible positioning does not match with the input string then we would return -1−1
Cont’d
• This is simple and efficient brute force approach. It compares the first character of pattern
with searchable text. If a match is found, pointers in both strings are advanced. If a match is
not found, the pointer to text is incremented and pointer of the pattern is reset. This process
is repeated till the end of the text.
• The naïve approach does not require any pre-processing. Given text T and pattern P, it
directly starts comparing both strings character by character.
• After each comparison, it shifts pattern string one position to the right.
• Following example illustrates the working of naïve string matching algorithm. Here,
• T = PLANINGANDANALYASIS and P = AND
• Here, ti and pj are indices of text and pattern respectively.
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
KMP- Knuth Morris and Pratt algorithm
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
Cont’d
 Design and Analysis of Algorithms
• Course Code: BCSE204L
• Course Type: Theory (ETH)
• Slot: A1+TA1 & & A2+TA2
• Class ID: VL2023240500901
VL2023240500902
A1+TA1 A2+TA2
Day Start End Day Start End
Monday 08:00 08:50 Monday 14:00 14:50
Wednesday 09:00 09:50 Wednesday 15:00 15:50
Friday 10:00 10:50 Friday 16:00 16:50

Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore

 Syllabus- Module 3
Module:3 String Matching Algorithms 5 hours

Naïve String-matching Algorithms,

KMP algorithm,
Rabin-Karp Algorithm,
Suffix Trees.

Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore

Suffix Trees (Introduction)
• Suffix trees are data structures used in string matching and manipulation.
• A suffix tree is built from the given text.
• After preprocessing the text (building the suffix tree of the text), we can
search for any pattern in O(m) time, where m is the length of the pattern.
• Here, all the suffixes of a given string in a way that enables efficient pattern
searching, substring retrieval, and other operations.

What is Suffix?
Suffix means a letter or group of letters that you add at the end of a word

Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore

Suffix Trees (Introduction)
A suffix tree for a given text is a compressed trie for all suffixes of the text.
Compressed Trie with the following array of words:
{bear, bell, bid, bull, buy, sell, stock, stop}

Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore

Suffix Trees (Introduction)
Compressed Trie with the following array of words: {bear, bell, bid, bull, buy, sell, stock, stop}
Compress Trie is obtained from standard trie by joining chains of single nodes. The nodes of a compressed trie can
be stored by storing index ranges at the nodes.

Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore

Build a Suffix Tree for a given text
• Suffix Tree is compressed trie of all suffixes,
1. Generate all suffixes of given text.
2. Consider all suffixes as individual words and build a compressed trie.

Example: “banana”
“banana\0”,
where ‘\0’ is string termination character.

Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore

Build a Suffix Tree for a given text
• Suffix Tree is compressed trie of all suffixes,
1. Generate all suffixes of given text.
2. Consider all suffixes as individual words and build a compressed trie.

Example: “banana” Following are all suffixes of “banana\0”

“banana\0”, banana\0
where ‘\0’ is string termination character. anana\0
nana\0
ana\0
na\0
a\0
\0
Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
Build a Suffix Tree for a given text
• Suffix Tree is compressed trie of all suffixes, Example: “banana”
1. Generate all suffixes of given text. “banana\0”,
2. Consider all suffixes as individual words and where ‘\0’ is string termination character.
build a compressed trie.

Following are all suffixes of “banana\0”

banana\0
anana\0
nana\0
ana\0
na\0
a\0
\0

Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore

Build a Suffix Tree for a given text
If we join chains of single nodes, we get the
following compressed trie, which is the Suffix
Tree for given text “banana\0”

Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore

Searching
Steps to search a pattern in the built Suffix Tree:
[Link] from the first character of the pattern and the root of the Suffix
Tree, do the following for every character:
a) For the current character of the pattern, if there is an edge from the current node of
the suffix tree, follow the edge.
b) If there is no edge, print "Pattern doesn't exist in the text" and return.
[Link] all characters of the pattern have been processed (i.e., there is a path
from the root for the characters of the given pattern), then print "Pattern
found".

Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore

Searching
Let us consider the example pattern as “nan” to see the
Steps to search a pattern in the built searching process. Following diagram shows the path
Suffix Tree: followed for searching “nan” or “nana”.
[Link] from the first character of the
pattern and the root of the Suffix Tree,
do the following for every character:
a) For the current character of the
pattern, if there is an edge from the
current node of the suffix tree,
follow the edge.
b) If there is no edge, print "Pattern
doesn't exist in the text" and return.
[Link] all characters of the pattern have
been processed (i.e., there is a path
from the root for the characters of the
given pattern), then print "Pattern
found". Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
Time Complexity
• Constructing the suffix tree: O(n^2)
• Searching for a pattern: O(m), where m is the length of the pattern.
• This is called a generalized suffix tree

Applications of Suffix Trees:

[Link] Searching.
[Link] the longest repeated substring.
[Link] the longest common substring.
[Link] the longest palindrome in a string.

Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore

Method Procedure Time Preproc Best in situation Other observations
complexity essing
(Matching
Time)
Brute Force Direct O(m*n) NA If text and pattern (m-n+1) index values
matching are very small are compared with
pattern

KMP LPS O(M+N) O(M) Overlapping and

non overlapping

Rabin Hash O(m*n) O(M) Best for repeated Two parameters, d

function O(M+N) patterns and prime number.

Suffix Tree Suffix tree O(M) O(N^2) Longest Repeated

Patterns

Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore

Dr. Venkata Phanikrishna B, SCOPE, VIT-Vellore
BCSE204L Design and Analysis of Algorithms

Module 3

Strings and Pattern Matching

Rabin-Karp

Dr. SIVARAJ C
Associate Professor Grade 1
School of Computer Science and Engineering,
Vellore Institute of Technology,
 Rabin-Karp
• The Rabin-Karp string searching algorithm calculates a hash
value for the pattern, and for each M-character subsequence
of text to be compared.
• If the hash values are unequal, the algorithm will calculate
the hash value for next M-character sequence.
• If the hash values are equal, the algorithm will do a Brute
Force comparison between the pattern and the M-character
sequence.
• In this way, there is only one comparison per text
subsequence, and Brute Force is only needed when hash
values match.
2
 Rabin-Karp Example
Hash value of “AAAAA” is 37
Hash value of “AAAAH” is 100

3
 Rabin-Karp Algorithm

pattern is M characters long

hash_p=hash value of pattern
hash_t=hash value of first M letters in body of text
do
if (hash_p == hash_t)
brute force comparison of pattern and selected section of text
hash_t= hash value of next section of text, one
character over
while (end of text)
4
 Hash Function
Let b be the number of letters in the alphabet. The text
subsequence t[i .. i+M-1] is mapped to the number

• Furthermore, given x(i) we can compute x(i+1) for the next

subsequence t[i+1 .. i+M] in constant time, as follows:

• In this way, we never explicitly compute a new value.

•We simply adjust the existing value as we move over 6one character.
Rabin-Karp Math Example
Let’s say that our alphabet consists of 10 letters.
our alphabet = a, b, c, d, e, f, g, h, i, j
Let’s say that “a” corresponds to 1, “b” corresponds to 2
and so on.
The hash value for string “cah” would be ...

3*100 + 1*10 + 8*1 = 318

7
 Rabin-Karp Mods
• If M is large, then the resulting value (~bM) will be enormous.
• For this reason, we hash the value by taking it mod a prime number
q.
• The mod function is particularly useful in this case due to several of
its inherent properties:
[(x mod q) + (y mod q)] mod q = (x+y) mod q
(x mod q) mod q = x mod q
For these reasons:
h(i)=((t[i] bM-1 mod q) +(t[i+1] bM-2 mod q) + … +(t[i+M-1] mod q))mod q

h(i+1) =( h(i) b mod q # Shift left one digit

-t[i] bM mod q #Subtract leftmost digit
+t[i+M] mod q ) #Add new rightmost digit
mod q
8
 Rabin-Karp Complexity
• If a sufficiently large prime number is used for the hash
function, the hashed values of two different patterns will
usually be distinct.
• If this is the case, searching takes O(N) time, where N is
the number of characters in the larger body of text.
• It is always possible to construct a scenario with a worst
case complexity of O(MN).
• This, however, is likely to happen only if the prime
number used for hashing is small.

9
Conclusion & Summary

• Core Concept: Uses hashing for fast pattern comparison; only

verifies potential matches when hash values align.
• Primary Advantage: Excellent for multi-pattern search (e.g.,
plagiarism detection).
• Time Complexity:
• Avg/Best: O(n + m)
• Worst: O(nm) (due to hash collisions)
• Susceptible to spurious hits; not the fastest option for single-
pattern searches (KMP/Boyer-Moore are better).
• A powerful, specialized tool—ideal for searching multiple
strings simultaneously, not a general-purpose replacement.