lOMoARcPSD|44613495
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 Samuel Wachira ndiang'ui ()
, lOMoARcPSD|44613495
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 = T.length
2 m = P.length
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 Samuel Wachira ndiang'ui ()
, lOMoARcPSD|44613495
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 Samuel Wachira ndiang'ui ()
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 Samuel Wachira ndiang'ui ()
, lOMoARcPSD|44613495
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 = T.length
2 m = P.length
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 Samuel Wachira ndiang'ui ()
, lOMoARcPSD|44613495
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 Samuel Wachira ndiang'ui ()
