MP - KMP

[nightmaregiba]

Hi everyone!
i have a question about Morris-Pratt and Knuth-Morris-Pratt algorithm

When we use MP and KMP, we need to find NEXT[j] table. Is there any differences between MP NEXT[j] table and KMP NEXT[j] table?

[Duthomhas]

Two names for the same algorithm.

It was developed by Knuth and Morris, and independently by Pratt.

MP just leaves off the K in KMP.

[nightmaregiba]

But i have a homework:

//--------------------------------------
P = 01011001011
a. Use MP to find NEXT[j] table
b. Use KMP to find NEXT[j] table

Compare two NEXT[j] table?
//--------------------------------------

I wonder if two NEXT[j] tables are different
Need ur help! Thanks in advance!

[nightmaregiba]

I was taught: Morris and Pratt developed that algorithm, and Knuth improve it with some changes in how to find NEXT table

[Duthomhas]

Oop. Looks like that's right. (Sorry.)

Here's something I googled that may help:
http://www-igm.univ-mlv.fr/~lecroq/string/node7.html#SECTION0070
http://www-igm.univ-mlv.fr/~lecroq/string/node8.html

[nightmaregiba]

ok thks