字符串匹配算法KMP

字符串匹配算法是一种高效率的字符串匹配算法，在面试中，经常会被问及到，考官经常会考察我们，代码如下：

       int[] nextKMP(string str)
        {
            int[] next = new int[str.Length];
            next[0] = -1;
            if (str.Length < 2)
                return next;
            next[1] = 0;
            int i = 2, j = 0;
            while(i < str.Length)
            {
                if(str[i-1] == str[j]){
                    next[i++] = ++j;
                }else{
                    j = next[j];
                    if(j == -1){
                        next[i++] = ++j;
                    }
                }
            }
            return next;
        }

        int executeKMP(string source, string pattern)
        {
            int[] next = nextKMP(pattern);
            int i = 0, j = 0;
            while (j < pattern.Length && i < source.Length)
            {
                if (source[i] == pattern[j])
                {
                    i++;
                    j++;
                }
                else
                {
                    j = next[j];
                    if (j == -1)
                    {
                        i++;
                        j++;
                    }
                }
            }
            return j < pattern.Length ? -1 : i - j;
        }