Question KMP algorithm to find a specific pattern

Please provide comments and solutions that are helpful to the author of this topic.

quentisa

Level 1
Thread author
Jan 6, 2023
11
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:
Code:
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.
 

About us

  • MalwareTips is a community-driven platform providing the latest information and resources on malware and cyber threats. Our team of experienced professionals and passionate volunteers work to keep the internet safe and secure. We provide accurate, up-to-date information and strive to build a strong and supportive community dedicated to cybersecurity.

User Menu

Follow us

Follow us on Facebook or Twitter to know first about the latest cybersecurity incidents and malware threats.

Top