Jacob_Thomas

KMP

Jan 28th, 2021
544
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  import java.util.*;
  2. class kmp{
  3.     public static void main(String args[]){
  4.         Scanner sc = new Scanner(System.in);
  5.         System.out.println("Enter the Text");
  6.         String text = sc.nextLine();
  7.         System.out.println("Enter the Pattern");
  8.         String pattern = sc.nextLine();
  9.         int t = text.length();
  10.         int p = pattern.length();
  11.         int lps[] = new int[t];
  12.         kmp.lps_function(pattern, p, lps);
  13.         int i = 0;
  14.         int j = 0;
  15.         while(i < t){
  16.             if(pattern.charAt(j) != text.charAt(i)){
  17.                 if(j == 0){
  18.                     i = i + 1;
  19.                 }
  20.                 else{
  21.                     j = lps[j - 1];
  22.                 }
  23.             }
  24.             else{
  25.                 i = i + 1;
  26.                 j = j + 1;
  27.             }
  28.             if(j == p){
  29.                 System.out.println("Pattern at index " + (i-j));
  30.                 j = lps[j-1];
  31.             }
  32.         }
  33.     }
  34.     public static void lps_function(String a, int n, int arr[]){
  35.         arr[0] = 0;
  36.         int i = 1;
  37.         int j = 0;
  38.         while(i < n){
  39.             if(a.charAt(i) == a.charAt(j)){
  40.                 arr[i] = j + 1;
  41.                 j = j + 1;
  42.                 i = i + 1;
  43.             }
  44.             else{
  45.                 if(j == 0){
  46.                     arr[i] = 0;
  47.                     i = i + 1;
  48.                 }
  49.                 else{
  50.                     j = arr[j-1];
  51.                 }
  52.             }
  53.         }
  54.     }
  55. }
RAW Paste Data