Untitled

class KMP_String_Matching { 
    void KMPSearch(String pat, String txt) { 
        int M = pat.length(); 
        int N = txt.length(); 
        int lps[] = new int[M]; 
        int j = 0; 

        computeLPSArray(pat, M, lps); 

        int i = 0; 
        while (i < N) { 
            if (pat.charAt(j) == txt.charAt(i)) { 
                j++; 
                i++; 
            } 
            if (j == M) { 
                System.out.println("Found pattern at index " + (i - j)); 
                j = lps[j - 1]; 
            } else if (i < N && pat.charAt(j) != txt.charAt(i)) { 
                if (j != 0) 
                    j = lps[j - 1]; 
                else
                    i = i + 1; 
            } 
        } 
    }