Consider the following brute-force algorithm for the substring matching problem: Input : Output: A String S of n characters, and a String P of m characters, where m ≤ n The index 1 ≤ i ≤ n where P begins as a substring of S

Consider the following brute-force algorithm for the substring matching problem: Input : Output:

A String S of n characters, and a String P of m characters, where m ≤ n

The index 1 ≤ i ≤ n where P begins as a substring of S. If P is not a substring of S, −1 is returned.

1: for i ← 1 to n − m + 1 do

2: hits ← 0

3: while hits < m and S[i + hits] = P[hits + 1] do

4: hits ← hits + 1

5: if hits = m then

6: return i

7: return −1 Algorithm

Algorithm 1: SubstringMatch(S, n, P, m)

Ques 1. Give an example of the worst-case input for this algorthim. How many character comparisons ( line 3 ) are made, as a function of n and m?

Ques 2. For a fixed n, what value for m would maximize the cost of the worst case?