Is it java? I don't understand java. Rewritten in python, it seems to work properly. So, you know how to get the lps table but don't know what to do with it next, do you?
The site you've linked to has a detailed explanation already. Basically all the fuss is about partial matches. For random strings the simple search can be quite good but for long series of identical characters the KMP algorithm is more efficient.
Let's rewrite the code from geeksforgeeks.org to see the difference:
Code: Select all
import sys
def lps(s):
tab = [0] * len(s)
t = tab[0]
for i in range(1, len(s)):
while t > 0 and s[i] != s[t]:
t = tab[t-1]
if s[i] == s[t]: t = t + 1
tab[i] = t
return tab
def simple_search(pattern, string):
patlen = len(pattern)
strlen = len(string)
i = j = 0
cnt = 0
while i < strlen:
cnt += 1
if pattern[j] == string[i]:
i += 1
j += 1
if j == patlen:
print("pattern found at %i" % (i - j))
else: continue
i = i - j + 1 # may need to backtrack i here
j = 0
print("Simple: %i iteration(s)" % cnt)
def kmp_search(pattern, string):
patlen = len(pattern)
strlen = len(string)
tab = lps(pattern)
i = j = 0
cnt = 0
while i < strlen:
cnt += 1
if pattern[j] == string[i]:
i += 1
j += 1
if j == patlen:
print("pattern found at %i" % (i - j))
else: continue
if j != 0:
j = tab[j-1] # use the table for j, don't backtrack i
else:
i += 1
print("KMP: %i iteration(s)" % cnt)
word = sys.argv[1]
text = sys.argv[2]
simple_search(word, text)
kmp_search(word, text)
The tests show that the KMP search needs fewer iterations to complete:
Code: Select all
root# python lps.py puppy "the puppy linux"
pattern found at 4
Simple: 21 iteration(s)
pattern found at 4
KMP: 15 iteration(s)
root# python lps.py aaaaa aaaaabaaaaaa
pattern found at 0
pattern found at 6
pattern found at 7
Simple: 34 iteration(s)
pattern found at 0
pattern found at 6
pattern found at 7
KMP: 16 iteration(s)
root# python lps.py AABA AABAACAADAABAABA
pattern found at 0
pattern found at 9
pattern found at 12
Simple: 34 iteration(s)
pattern found at 0
pattern found at 9
pattern found at 12
KMP: 20 iteration(s)