CODEWITHSUNDEEP
algorithmstring-comparisonstring-matchingknuth-morris-pratt
SSMA
SSMA

Reputation: 497

Knuth Morris Pratt algorithm comparison

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,

Upvotes: 1

Views: 708

Answers (1)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70939

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[SPi] and then against P[SPSPi+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.

Upvotes: 0

Related Questions