// C# program for implementation of KMP pattern 

// searching algorithm 

using System; 

​

public class Program { 

​

    public static int KMPSearch(string pat, string txt) 

    { 

        int m = pat.Length; 

        int n = txt.Length; 

​

        // create lps[] that will hold the longest 

        // prefix suffix values for pattern 

        int[] lps = new int[m]; 

        int j = 0; // index for pat[] 

​

        // Preprocess the pattern (calculate lps[] array) 

        ComputeLPSArray(pat, m, lps); 

​

        int i = 0; // index for txt[] 

        while (i < n) 

        { 

            if (pat[j] == txt[i]) 

            { 

                j++; 

                i++; 

            } 

            if (j == m) 

            { 

                Console.Write("Found pattern at index " + (i - j)); 

                return (i - j);

                // j = lps[j - 1]; 

            } 

​

            // mismatch after j matches 

            else if (i < n && pat[j] != txt[i]) 

            { 

                // Do not match lps[0..lps[j-1]] characters, 

                // they will match anyway 

                if (j != 0) 

                    j = lps[j - 1]; 

                else

                    i = i + 1; 

            } 

        }

        return -1;

    } 

​

    private static void ComputeLPSArray(string pat, int m, int[] lps) 

    { 

        // length of the previous longest prefix suffix 

        int len = 0; 

        int i = 1; 

        lps[0] = 0; // lps[0] is always 0 

​

        // the loop calculates lps[i] for i = 1 to M-1 

        while (i < m) 

        { 

            if (pat[i] == pat[len]) 

            { 

                len++; 

                lps[i] = len; 

                i++; 

            } 

            else // (pat[i] != pat[len]) 

            { 

                // This is tricky. Consider the example. 

                // AAACAAAA and i = 7. The idea is similar 

                // to search step. 

                if (len != 0) 

                { 

                    len = lps[len - 1]; 

​

                    // Also, note that we do not increment i here 

                } 

                else // if (len == 0) 

                { 

                    lps[i] = len; 

                    i++; 

                } 

            } 

        } 

    } 

​

    // Driver program to test above function 

    public static void Main() 

    { 

        string txt = "ABABDABACDABABCABAB"; 

        string pat = "ABABCABAB"; 

        Program.KMPSearch(pat, txt); 

    } 

} 

​