The brute-force pattern matching algorithm on the slides runs until either a. A
ID: 3701991 • Letter: T
Question
The brute-force pattern matching algorithm on the slides runs until either
a. A match is found, or
b. All placements of the pattern have been tried.
Write the pseudocode for an algorithm such that it reports all occurrences of a pattern P with the number of shifts needed to achieve that.
Brute-Force Pattern Matching Algorithm BruteForceMatch(T, P) The brute-force pattern matching algorithm compares the pattern P with the text T for each possible shift of P relative to T, until either - a match is found, or Input text T of size n and pattern P of size m Output starting index of a substring of T equal to P or-1 if no such substring exists test shift i of the pattern while JExplanation / Answer
Algorithm BruteForceMatch(T, P)
Input : Text T of size n and pattern P of size m
Output : nothing
total_occurance <- 0
total_shift <- 0
for i <- 0 to n - m
{ test shift i of the pattern }
total_shift <- total_shift + 1
j <- 0
while j < m / T[i + j] = P[j]
j <- j + 1
end while
if j = m
total_occurance <- total_occurance + 1
Display 'Occurance : ' . total_occurance
Display 'Position -> ' . i
Display 'Shift needed -> ' . total_shift
end if
end for
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.