Academic Integrity: tutoring, explanations, and feedback — we don’t complete graded work or submit on a student’s behalf.

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 J

Explanation / 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

Hire Me For All Your Tutoring Needs
Integrity-first tutoring: clear explanations, guidance, and feedback.
Drop an Email at
drjack9650@gmail.com
Chat Now And Get Quote