Question VI $[$String Matching$]$: Comparing Algorithms

You are given the following text and pattern:

Text: "ababcabcabababd"

Pattern: "ababd"

$(6$ points$)$ Using the Brute Force Algorithm, manually simulate the stringmatching process step by step and identify the total number of comparisons made.

$(10$ points$)$ Using the Knuth$-$Morris$-$Pratt Algorithm, simulate the same process step by step, showing how the prefix table is used to skip unnecessary comparisons, and determining the total number of comparisons.

$(2$ points$)$ Compare the number of character comparisons made in both approaches and explain why KMP is more efficient for this example.