In this exercise we deal with the problem of string

Problem 46E

In this exercise we deal with the problem of string matching.

a) Explain how to use a brute-force algorithm to find the first occurrence of a given string of m characters, called the target, in a string of n characters, where m ≤ n, called the text. [Hint: Think in terms of finding a match for the first character of the target and checking successive characters for a match, and if they do not all match, moving the start location one character to the right.]

b) Express your algorithm in pseudocode.

c) Give a big-O estimate for the worst-case time complexity of the brute-force algorithm you described.

Solution:

Step 1

In this problem we have to write how to use a brute-force algorithm to find the first occurrence of a given string of m characters, called the target, in a string of n characters, where m ≤ n, called the text. Then we need to write the pseudocode for the algorithm.

And finally we need to estimate the worst-case time complexity of the brute-force algorithm.