KMP

 import java.util.*;
class kmp{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the Text");
        String text = sc.nextLine();
        System.out.println("Enter the Pattern");
        String pattern = sc.nextLine();
        int t = text.length();
        int p = pattern.length();
        int lps[] = new int[t];
        kmp.lps_function(pattern, p, lps);
        int i = 0;
        int j = 0;
        while(i < t){
            if(pattern.charAt(j) != text.charAt(i)){
                if(j == 0){
                    i = i + 1;
                }
                else{
                    j = lps[j - 1];
                }
            }
            else{
                i = i + 1;
                j = j + 1;
            }
            if(j == p){
                System.out.println("Pattern at index " + (i-j));
                j = lps[j-1];
            }
        }
    }
    public static void lps_function(String a, int n, int arr[]){
        arr[0] = 0;
        int i = 1;
        int j = 0;
        while(i < n){
            if(a.charAt(i) == a.charAt(j)){
                arr[i] = j + 1;
                j = j + 1;
                i = i + 1;
            }
            else{
                if(j == 0){
                    arr[i] = 0;
                    i = i + 1;
                }
                else{
                    j = arr[j-1];
                }
            }
        }
    }
}