5. Design Horspools algorithm for string matching. Apply Horspools algorithm to find the pattern BARBER in the text: JIM_SAW_ME_IN_A_BARBERSHOP
Answer:
Horspool’s algorithm is an efficient string matching algorithm that improves over the brute-force approach by skipping characters using a precomputed shift table. It matches characters from right to left in the pattern and shifts the pattern intelligently upon mismatches.
Shift Table Construction
Let the pattern be of length m. The shift table t(c) is built as:
- If character c is not in the first m – 1 characters of the pattern:
t(c) = m - If character c is in the pattern before the last character:
t(c) = m – 1 – last_index(c)
For the pattern BARBER (length m = 6):
We scan from left to right for first m – 1 = 5 characters:
All other characters get default shift = 6.
So, final shift table entries (selected):
- t(B) = 2
- t(A) = 4
- t(R) = 3
- t(E) = 1
- t(any other character) = 6
Algorithm Steps
- Construct the shift table for the pattern.
- Align the pattern against the start of the text.
- While the pattern has not gone past the end of the text:
- Compare the pattern from right to left.
- If all characters match, return the match position.
- If mismatch occurs, shift the pattern to the right by t(c), where c is the text character aligned with the pattern’s last character.
HorspoolMatching(P[0..m−1], T[0..n−1]):
ShiftTable(P)
i ← m−1
while i ≤ n−1 do
k ← 0
while k ≤ m−1 and P[m−1−k] = T[i−k] do
k ← k + 1
if k = m then
return i−m+1
else
i ← i + t(T[i])
return -1
Apply to Pattern BARBER and Text:
Pattern: BARBER
Text: JIM_SAW_ME_IN_A_BARBERSHOP (underscore _ represents space)
Pattern length = 6, m = 6
Text length = 27
We begin with i = m – 1 = 5
We continue matching and shifting as follows:
Final Answer:
Pattern BARBER is found in the text JIM_SAW_ME_IN_A_BARBERSHOP starting at index 16.
Time Complexity:
