👀 Views: 68 💬 Answers: 1 📅 Created: 2025-06-06

algorithm string-search kmp Java

This might be a silly question, but I'm currently implementing the Knuth-Morris-Pratt (KMP) algorithm for substring search in Java, but I'm working with an scenario where the pattern index seems to misalign with the input string index. This is causing incorrect matches to be reported. Here’s the relevant portion of my code: ```java public class KMP { private int[] lps; public KMP(String pattern) { this.lps = new int[pattern.length()]; computeLPSArray(pattern); } private void computeLPSArray(String pattern) { int length = 0; lps[0] = 0; for (int i = 1; i < pattern.length(); ) { if (pattern.charAt(i) == pattern.charAt(length)) { length++; lps[i] = length; i++; } else { if (length != 0) { length = lps[length - 1]; } else { lps[i] = 0; i++; } } } } public void search(String text, String pattern) { int i = 0; // index for text int j = 0; // index for pattern while (i < text.length()) { if (pattern.charAt(j) == text.charAt(i)) { i++; j++; } if (j == pattern.length()) { System.out.println("Found pattern at index " + (i - j)); j = lps[j - 1]; } else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) { if (j != 0) { j = lps[j - 1]; } else { i++; } } } } } ``` When I run the search method with the text `"ababcabcabababd"` and the pattern `"ababd"`, it incorrectly reports that the pattern is found at index 10, which is not the case. I’ve already validated my input strings and ensured they are correctly formatted. I suspect that the scenario might be related to how I’m managing the indices, but I need to pinpoint the exact question. I also tried adding debug print statements, which show that my `lps` array is generated correctly. Here’s how I'm calling the search: ```java KMP kmp = new KMP("ababd"); kmp.search("ababcabcabababd", "ababd"); ``` I’m using Java 11. Can anyone spot what's going wrong or suggest a fix? Thanks in advance! I'm working on a API that needs to handle this. Thanks in advance!