👀 Views: 257 💬 Answers: 1 📅 Created: 2025-06-09

algorithm kmp string-matching Python

I'm not sure how to approach I've searched everywhere and can't find a clear answer. I'm working on a string searching feature using the Knuth-Morris-Pratt (KMP) algorithm in Python, but I'm working with false positives in my output where the pattern is found within a substring of the text. My implementation seems to be mostly correct, but when I run the pattern `abc` on the text `abcpqrabcabc`, it incorrectly returns a match at the position of the substring `abcpqr`. I've double-checked my prefix table generation, and it looks fine. Here's a snippet of my code for reference: ```python def kmp_search(pattern, text): m = len(pattern) n = len(text) lps = [0] * m j = 0 # index for pattern compute_lps(pattern, lps) i = 0 # index for text while i < n: if pattern[j] == text[i]: i += 1 j += 1 if j == m: print(f'Pattern found at index {i - j}') j = lps[j - 1] elif i < n and pattern[j] != text[i]: if j != 0: j = lps[j - 1] else: i += 1 def compute_lps(pattern, lps): length = 0 # length of previous longest prefix suffix lps[0] = 0 # lps[0] is always 0 i = 1 while i < len(pattern): if pattern[i] == pattern[length]: length += 1 lps[i] = length i += 1 else: if length != 0: length = lps[length - 1] else: lps[i] = 0 i += 1 ``` I've also added print statements to debug the values of `i`, `j`, and the `lps` array during execution, but they all seem accurate. The scenario only appears with certain combinations of text and patterns. I suspect it might have to do with how I'm handling the indices when a match is found. Has anyone faced a similar scenario with KMP? What could be going wrong here? I'm working on a API that needs to handle this. Any help would be greatly appreciated! The project is a REST API built with Python. Cheers for any assistance!