lOMoARcPSD|61619697
Dsa Module - 5 notes
Data Structure and Algorithms for Problem solving (Visvesvaraya Technological
University)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
Module – 5
String - Matching Algorithms
1. The Naive String-Matching Algorithm
The naive algorithm finds all valid shifts using a loop that checks the condition
P (1.. m) = T (s + 1… s + m) for each of the n - m + 1 possible values of s.
NAIVE-STRING-MATCHER (T, P)
1 n = [Link]
2 m = [Link]
3 for s = 0 to n - m
4 if P [1..m] == T [s + 1 … s + m]
5 print “Pattern occurs with shift” s
Show the comparisons the naive string matcher makes for the pattern P = 0001 in the text
T = 000010001010001.
Text (T): 000010001010001
Pattern (P): 0001 (length m = 4)
Text length: n = 15
Number of shifts: n - m + 1 = 12
We try shifts from s = 0 to 11, comparing substrings T[s:s+4] with P.
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
Shift s T substring T[s:s+4] Compare with P Match? Comparisons
0 0000 0001 ✗ 4 (mismatch at 4th)
1 0000 0001 ✗ 4
2 0001 0001 ✓ 4
3 0010 0001 ✗ 1
4 0100 0001 ✗ 1
5 1000 0001 ✗ 1
6 0001 0001 ✓ 4
7 0010 0001 ✗ 1
8 0101 0001 ✗ 1
9 1010 0001 ✗ 1
10 0100 0001 ✗ 1
11 1001 0001 ✗ 1
Matches found at shifts: s = 2 and s = 6
Total comparisons: 4+4+4+1+1+1+4+1+1+1+1+1 = 24
Suppose that all characters in the pattern P are different. Show how to accelerate NAIVE-
STRING-MATCHER to run in time O(n).
If all characters in P are distinct:
• When a mismatch is found at position j, we can safely shift P by j positions instead of
just 1.
• Since no prefix of P is a suffix, there's no point in checking intermediate shifts.
This results in skipping comparisons and advances faster, which leads to O(n) time in the best
and average cases.
You can modify the loop:
s=0
while s <= n - m:
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
match = True
for j in range(m):
if T[s + j] != P[j]:
match = False
break
if match:
print("Pattern occurs with shift", s)
s += m # skip m positions if matched
else:
s += 1 # or s += j when j > 0 and all P chars are distinct
32.1-4: Pattern with gap character }
The gap character } can match any substring (even empty). This is similar to wildcard or regex
matching.
Let’s solve it using dynamic programming, like regular expression matching.
Let:
• T be the text of length n
• P be the pattern of length m (with possible gap characters)
• Define a 2D boolean DP table dp[i][j], where dp[i][j] = True means pattern P[0..i-1]
matches text T[0..j-1].
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
Algorithm:
def match_with_gap(P, T):
m, n = len(P), len(T)
dp = [[False] * (n+1) for _ in range(m+1)]
dp[0][0] = True
# Fill first row (pattern with gaps only)
for i in range(1, m+1):
if P[i-1] == '}':
dp[i][0] = dp[i-1][0]
else:
break
for i in range(1, m+1):
for j in range(1, n+1):
if P[i-1] == '}':
# Match gap: either extend the match (dp[i][j-1]) or skip gap (dp[i-1][j])
dp[i][j] = dp[i-1][j] or dp[i][j-1]
elif P[i-1] == T[j-1]:
dp[i][j] = dp[i-1][j-1]
return any(dp[m][j] for j in range(n+1))
Time Complexity:
• O(mn) → Polynomial-time algorithm
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
2. Rabin-Karp algorithm
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
3. String Matching with Finite automata
Algorithm:
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
Explanation:
• Starts at state 0
• Moves through states as characters match
• Reaches state 7 at i = 8 → indicates a match of the entire pattern ending at position 8
The match is on T[2..8] = abababaca
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
4. Knuth-Morris-Pratt Algorithm
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
Trace the KMP algorithm for the following: T[]=”bacbababaabcbab” P[]=”ababaca”
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
i T[i] j P[j] Match? Action
0 b 0 a No i++
1 a 0 a Yes i++, j++
2 c 1 b No j = lps[j-1] = 0
2 c 0 a No i++
3 b 0 a No i++
4 a 0 a Yes i++, j++
5 b 1 b Yes i++, j++
6 a 2 a Yes i++, j++
7 b 3 b Yes i++, j++
8 a 4 a Yes i++, j++
9 a 5 c No j = lps[4] = 3
9 a 3 b No j = lps[2] = 1
9 a 1 b No j = lps[0] = 0
9 a 0 a Yes i++, j++
10 b 1 b Yes i++, j++
11 c 2 a No j = lps[1] = 0
11 c 0 a No i++
12 b 0 a No i++
13 a 0 a Yes i++, j++
14 b 1 b Yes i++, j++
Now i = 15 (end of text), and j = 2 — since j ≠ len(P), no match found.
Final Result:
No full match of pattern "ababaca" in text "bacbababaabcbab"
KMP efficiently skipped unnecessary comparisons using the LPS table.
Let me know if you want a diagram or visual representation too!
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
5. Boyer – Moore algorithms
Downloaded by Kavya R (kavya.r.273.3@[Link])
lOMoARcPSD|61619697
Downloaded by Kavya R (kavya.r.273.3@[Link])