knutt morris pratt O(m+n)

import java.util.*;
class kmp
{
    static Scanner t = new Scanner(System.in);
    public static int[] substring(char pattern[])
    {
        int lps[] = new int[pattern.length];
        lps[0] = 0;
        int j=0;
        int i;
        for(i =1;i<pattern.length;)
        {
            if(pattern[i]==pattern[j])
            {
                lps[i] = j+1;
                i++;
                j++;
            }
            else
            {
                if(j!=0)
                    j = lps[j-1];
                else
                {
                    lps[i]=0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static int kmp(char text[],char pattern[])
    {
            int lps[] = substring(pattern);
            for(int i=0;i<lps.length;i++)
                System.out.println(lps[i]+" ");
            int j=0,i,k=-1;
            for(i=0;i<text.length&&j<pattern.length;)
            {
                if(j==0)
                    k=i;
                if(pattern[j]==text[i])
                {
                    i++;
                    j++;
                }
                else
                {
                    if(j!=0)
                        j=lps[j-1];
                    else i++;
                }
            }
            if(j==pattern.length)
                return i-j+1;
            return -1;
    }
    public static void main(String args[])
    {
        System.out.println("Enter text\t");
        String text = t.nextLine();
        System.out.println("Enter pattern\t");
        String pattern  = t.nextLine();
        int t =  kmp(text.toCharArray(),pattern.toCharArray());
        if(t!=-1)
            System.out.println("pattern found at "+t);
        else System.out.println("pattern not found");
    }
}