Invented by Donald Knuth and Vaughan Pratt

independently by James H Morris

In the year 1977, all the three jointly published KMP Algorithm.

Step 1 - Define a one dimensional array with the size equal to the length of the Pattern. (LPS[size])

Step 2 - Define variables i & j. Set i = 0, j = 1 and LPS[0] = 0.

Step 3 - Compare the characters at Pattern[i] and Pattern[j]

Step 4 - If both are matched then set LPS[j] = i+1 and increment both i & j values by one. Goto to Step 3.

Step 5 - If both are not matched then check the value of variable 'i'. If it is '0' then set LPS[j] = 0 and increment 'j' value by one, if it is not '0' then set i = LPS[i-1]. Goto Step 3.

Step 6- Repeat above steps until all the values of LPS[] are filled.