Scribd
Upload
10 views8 pages

String Matching Algorithms Overview

The document discusses various string matching algorithms, including the Naive String Matching, Rabin-Karp, and KMP algorithms, detailing their algorithms, time and space complexities. The Naive algorithm has a time complexity of O(n-m+1) and space complexity of O(1), while Rabin-Karp has average and best case complexities of O(m+n) and a worst case of O(mn). The KMP algorithm offers a consistent time complexity of O(n) and a space complexity of O(m) due to pre-processing requirements.

Uploaded by

pandeysatyam1802
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views8 pages

String Matching Algorithms Overview

The document discusses various string matching algorithms, including the Naive String Matching, Rabin-Karp, and KMP algorithms, detailing their algorithms, time and space complexities. The Naive algorithm has a time complexity of O(n-m+1) and space complexity of O(1), while Rabin-Karp has average and best case complexities of O(m+n) and a worst case of O(mn). The KMP algorithm offers a consistent time complexity of O(n) and a space complexity of O(m) due to pre-processing requirements.

Uploaded by

pandeysatyam1802
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

String Matching algorithms

Naive String Matching Algorithm


• Algorithm
----------------------------------------------------------------
NAIVE_STRING_MATCHING(T, P)
n ← length [T]
m ← length [P]
for i ← 0 to n – m
do
if P[1… m] == T[i+1…i+m]
Then
print "Pattern occurs with shift" s
end
end
Complexity analysis
Time complexity
• In the naive string matching algorithm, the time
complexity of the algorithm comes out to be
O(n-m+1), where n is the size of the input string
and m is the size of the input pattern string.
Space complexity
• In the naive string matching algorithm, the space
complexity of the algorithm comes out to
be O(1).
Rabin Karp algorithm

n = [Link]
m = [Link]
h = dm-1 mod q
p=0
t0 = 0
for i = 1 to m
p = (dp + p[i]) mod q
t0 = (dt0 + t[i]) mod q
for s = 0 to n - m
if p = ts
if p[1.....m] = t[s + 1..... s + m]
print "pattern found at position" s
Complexity
Time Complexity:
• The average case and best case complexity of
Rabin-Karp algorithm is O(m + n) and the worst
case complexity is O(mn).
• The worst-case complexity occurs when spurious
hits occur a number for all the windows.
Space Complexity: O(1)
• It uses constant space. So, the space complexity
is O(1).
Limitations of Rabin-Karp Algorithm

Spurious Hit
• When the hash value of the pattern matches
with the hash value of a window of the text
but the window is not the actual pattern then
it is called a spurious hit.
• Spurious hit increases the time complexity of
the algorithm. In order to minimize spurious
hit, we use modulus. It greatly reduces the
spurious hit.
KMP Algorithm
findPrefix(pattern, m, prefArray) kmpAlgorithm(text, pattern)
Begin
Begin
n := size of text
length := 0 m := size of pattern
prefArray[0] := 0 call findPrefix(pattern, m, prefArray)
for all character index „i‟ of pattern, do while i < n, do
if pattern[i] = pattern[length], then if text[i] = pattern[j], then
increase length by 1 increase i and j by 1
if j = m, then
prefArray[i] := length
print “The location (i-j) as there is the
else pattern”
if length ≠ 0 then j := prefArray[j-1]
length := prefArray[length - 1] else if i < n AND pattern[j] ≠ text[i] then
decrease i by 1 if j ≠ 0 then
else j := prefArray[j - 1]
else
prefArray[i] := 0
increase i by 1
done done
End End
Complexity
• Time Complexity
• Time complexity of the search algorithm
is O(n).
• These complexities are the same, no matter
how many repetitive patterns are in.
• Space Complexity
It has a space complexity of O (m) because
there’s some pre-processing involved.

You might also like