Question KMP algorithm to find a specific pattern

[quentisa]

I'm trying to implement the KMP algorithm to find a specific pattern within a larger string, but I'm having trouble understanding how to implement the search function properly. I've got the partial match table construction working correctly, but when I try to use it in the search function, the algorithm is not returning the correct results. I've tried going through the documentation and examples like this, but I'm still not sure what I'm doing wrong.
Here's an example of the code I've written for the search function:

def kmp_search(text, pattern, partial_match_table):
n = len(text)
m = len(pattern)
j = 0
for i in range(n):
while j > 0 and text[i] != pattern[j]:
j = partial_match_table[j - 1]
 if text[i] == pattern[j]:
j += 1
 if j == m:
return i - j + 1
return -1

I'm not sure if there's a mistake in this code or if I'm not understanding how to properly use the partial match table in the search function. I would really appreciate any help in understanding how to correctly implement the search function so that the KMP algorithm can work properly.

 

[mithun123]

MalwareTips is not the right forum to ask this question. You could have looked into places like Stackoverflow or Wiki itself to get the answer. Anyways if you are looking for a simple article on KMP algo complexity, you can try this out KMP Algorithm Explained In Plain English – W3 Spot.