Pattern Search using KMP
This program searches for pattern using KMP algorithm.
Problem Statement
Write a Java program to search "needle" in "haystackneedlehayneedle".
Source Code
| 1 | public class KMPPatternSearch { |
| 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 Pattern Search"); |
| 15 | String txt="haystackneedlehayneedle", pat="needle"; |
| 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 Pattern Search Found at index 8 Found at index 15
Explanation
The LPS array is precomputed for the pattern "needle", enabling the search to skip redundant character comparisons by using known prefix-suffix overlaps, demonstrating efficient KMP-based pattern searching.