Substring Search using KMP
This program searches substring using KMP algorithm.
Problem Statement
Write a Java program to search "abc" in "abxabcabcaby" using KMP.
Source Code
| 1 | public class KMPSubstringSearch { |
| 2 | public static void computeLPS(String pat,int[] lps){ |
| 3 | int len=0,i=1; |
| 4 | while(i<pat.length()){ |
| 5 | if(pat.charAt(i)==pat.charAt(len)){ |
| 6 | lps[i++]=++len; |
| 7 | } else { |
| 8 | if(len!=0) len=lps[len-1]; |
| 9 | else lps[i++]=0; |
| 10 | } |
| 11 | } |
| 12 | } |
| 13 | public static void main(String[] args) { |
| 14 | System.out.println("Eduinq KMP Substring Search"); |
| 15 | String txt="abxabcabcaby", pat="abc"; |
| 16 | int[] lps=new int[pat.length()]; |
| 17 | computeLPS(pat,lps); |
| 18 | int i=0,j=0; |
| 19 | while(i<txt.length()){ |
| 20 | if(pat.charAt(j)==txt.charAt(i)){ i++; j++; } |
| 21 | if(j==pat.length()){ |
| 22 | System.out.println("Found at index "+(i-j)); |
| 23 | j=lps[j-1]; |
| 24 | } else if(i<txt.length() && pat.charAt(j)!=txt.charAt(i)){ |
| 25 | if(j!=0) j=lps[j-1]; else i++; |
| 26 | } |
| 27 | } |
| 28 | } |
| 29 | } |
Program Output
Eduinq KMP Substring Search Found at index 3 Found at index 6
Explanation
The LPS (longest prefix suffix) array is precomputed for the pattern, allowing the search to skip redundant comparisons by falling back to known prefix matches instead of restarting, demonstrating the efficient KMP substring search algorithm.