namespace AuDDebuggen2

{

    public class KMP

    {

        //method to calculate the next array 

        public int[] ComputeKMPTable(string pattern)

        {

            int m = pattern.Length;

            int[] next = new int[m];

            int i = 0, j = -1;

            next[0] = 0;

            while (i < m)

            {

                if (pattern[i] == pattern[j])

                {

                    j++;

                    next[i] = j;

                    i++;

                }

                else

                {

                    if (j != 0)

                    {

                        j = next[j - 1];

                    }

                    else

                    {

                        next[i] = 0;

                        i++;

                    }

                }

            }

​

            return next;

        }

​

        // KMP-Searchmethod

        public int KMPSearch(string text, string pattern)

        {

            int n = text.Length;

            int m = pattern.Length;

            int[] next = ComputeKMPTable(pattern);

            int i = 0, j = 0;

            while (i < n)

            {

                if (pattern[j] == text[i])

                {

                    i++;

                    j++;

                }

​

                if (j == m)

                {

                    return i - j; //the complete match found, the start index returned 

                }

                else if (i < n && pattern[j] != text[i])

                {

                    if (j != 0)

                    {

                        j = next[j - 1];

                    }

                    else

                    {

                        i++;

                    }

                }

            }

​

            return -1; // match not found 

        }

    }

}