Knuth Morris Pratt algorithm comparison

Question

I have been studying for my exams when I came across with this problem, guys help please

For any alignment of pattern P and text T, suppose a mismatch occurs at P[i+1] and T[k] during the execution of KMP algorithm How many times does T[k] come into comparison in total during the execution of KMP algorithm (SPi is non-optimized)

the possible solutions I came across with are

1. i-SPi
2. SPi+1
3. n-i
4. n-SPi

but all of them fail on some scenarios,

Answer 1

There is no single answer for all cases.

Still you can give an upper bound on the number of comparisons and it is found if all symbols in P are the same. Try and compute that.

If this is not enough try using this property: KMP will compare T[k] against P[SP_i] and then against P[SP_SPi+1] and so on until one of two options happens:

• The given letter matches T[k]
• The value of the given SP is 0

The two above may happen in many different ways depending on P and T and so it is impossible to give a closed formula.