The pseudo code of the string matching algorithm is given below: Note that the p
ID: 440540 • Letter: T
Question
The pseudo code of the string matching algorithm is given below: Note that the pseudo code below tests only for the occurrence (or the absence) of the search pattern in the search string. You will have to slightly modify the pseudo code to count the number of occurrences of the pattern in the string as well as the total number of character comparisons.
ALGORITHM BruteForceStringMatch(T[0..n - 1], P[0..m - 1])
// Implements brute-force string matching
// Input: An array T[0..n - 1] of n characters representing a text and
// an array P[0..m - 1] of m characters representing a pattern
// Output: The index of the first character in the text that starts a
// matching substring or -1 if the search is unsuccessful
for i <- 0 to n - m do
j <- 0
while j < m and P[j] = T[i + j] do
j <- j + 1
if j = m return i
return -1
Explanation / Answer
This is the modified algorithim for brute force String matching ...
Check it out...
ALGORITHM BruteForceStringMatch(T[0..n - 1], P[0..m - 1])
// Implements brute-force string matching
// Input: An array T[0..n - 1] of n characters representing a text and
// an array P[0..m - 1] of m characters representing a pattern
// Output: The index of the first character in the text that starts a
// matching substring or -1 if the search is unsuccessful
1 --- > int count =0 // intializing a counter variable
2 ----> int noOfCharComp = 0 // intializing another counter variable for counting no of comparasions.
3 ----> for i <- 0 to n-m do
3.1 ----> j <- 0
3.2 ----> while j < m and P[j] = T[i + j] do
3.2.1 ---> noOfCharComp ++ // this will determine the no of Charcter matchings done.
3.2.2 ---> j <- j + 1
3.3 ---> if j = m
3.3.1 ---> count =count +1 // count variable will be used to determine the no of Pattern occurance
4 ---->if count >0
4.1 ---> print "No of charcter comparasion is "+noOfCharComp
4.2 --->return count //This will return the no of occuarance of pattern in the target String .
5 ----> else if count =0
5.1 ---> print "string pattern not found "
5.2 ---> return -1
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.