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

LPS array precomputes longest prefix suffix. - Efficient substring search avoids rechecking. - Together demonstrates KMP algorithm. Conclusion: Shows how to search substring using KMP.

Quick Links to Explore