👀 Views: 14 💬 Answers: 1 📅 Created: 2025-08-25

algorithm string-matching kmp python Python

I'm working on a personal project and I'm implementing the Knuth-Morris-Pratt (KMP) algorithm for substring search in Python, but I'm working with false positives in my results. Specifically, when I try to find the substring in the main string, it sometimes reports a match even when it shouldn't. Here's a simplified version of my code: ```python def compute_lps(pattern): lps = [0] * len(pattern) j = 0 # length of previous longest prefix suffix i = 1 while i < len(pattern): if pattern[i] == pattern[j]: j += 1 lps[i] = j i += 1 else: if j != 0: j = lps[j - 1] else: lps[i] = 0 i += 1 return lps def kmp_search(text, pattern): m = len(pattern) n = len(text) lps = compute_lps(pattern) i = 0 # index for text j = 0 # index for pattern results = [] while i < n: if pattern[j] == text[i]: i += 1 j += 1 if j == m: results.append(i - j) j = lps[j - 1] elif i < n and pattern[j] != text[i]: if j != 0: j = lps[j - 1] else: i += 1 return results ``` When I run the search, I get results that include positions where the pattern should not be found. For example, searching for "abc" in the text "ababcabc" returns indices 2 and 5, which is expected, but it also incorrectly suggests index 1 as a match, which shouldn't be the case. I've verified that the pattern is indeed not found at index 1, and my `lps` array seems to be computed correctly. I suspect there may be a logic behavior in how I'm checking matches or possibly an off-by-one behavior, but I need to seem to pinpoint the scenario. Any insights into what might be going wrong would be greatly appreciated! I'm using Python 3.9.7. For context: I'm using Python on Ubuntu. Thanks in advance!