For a given string P=p1p2...pm, a next(i) function, for 1im, is defined as follows:

next(i) = the maximum j (0

next(i) = 0 if no such j exists.

a) Compute next table for pattern string ``P=abaabab''.

b) Suppose that in the KMP string matching algorithm, we have first five characters of P matched and there is a mismatch at the sixth character, explain how the next table in a) is used in the situation.