KMP Search

/* JAVA IMPLEMENTATION */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class KMPSearch {

    /**
     * @param args
     */
public static void main(String[] args) throws IOException {
       
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String text= new String(br.readLine());
        String pattern=new String(br.readLine());
        kmpSearch(text,pattern);

    }

    private static void kmpSearch(String text, String pattern) {
       
        int text_index=0,pattern_index=0;
        int text_length=text.length();
        int pattern_length=pattern.length();
        int lpt[]=new int[pattern_length+1];
        computeLongestPrefixTable(pattern,pattern_length,lpt);
        while(text_index<text_length)
        {
            if(text.charAt(text_index)==pattern.charAt(pattern_index))
            {
                text_index++;
                pattern_index++;
            }
            else if(text.charAt(text_index)!=pattern.charAt(pattern_index))
            {
                if(pattern_index!=0)
                {
                    pattern_index=lpt[pattern_index-1];
                }
                else
                {
                    text_index++;
                }
            }
            if(pattern_index==pattern_length)
            {
                System.out.println("PATTERN MATCH AT "+(text_index-pattern_index));
                pattern_index=lpt[pattern_index-1];
            }
           
        }
       
    }

    // computing pattern table for prefix and suffix matching
    private static void computeLongestPrefixTable(String pattern,
            int pattern_length, int[] lpt) {
       
        int length=0;
        int index=0;
        lpt[index++]=0; // first element is always  zero
       
        while(index<pattern_length)
        {
            if(pattern.charAt(length)==pattern.charAt(index))
            {
                length++;
                lpt[index]=length;
                index++;
            }
            else
            {
                if(length!=0)
                {
                    length=lpt[length-1];
                }
                else
                {
                    lpt[index++]=0;
                }
            }
        }
    }


}