KMP算法

string tString = "ababcabcacbab";
string pString = "abcac";
int[] next = cal_next(pString, new int[pString.Length], pString.Length);
int locationId = KMP(tString, tString.Length, pString, pString.Length, next);

 public static int[] cal_next(string str, int[] next, int len)
        {
            int i, j;
            next[0] = -1;
            for (i = 1; i < len; i++)
            {
                j = next[i - 1];
                while (str[j + 1] != str[i] && (j >= 0))
                {
                    j = next[j];
                }
                if (str[i] == str[j + 1])
                {
                    next[i] = j + 1;
                }
                else
                {
                    next[i] = -1;
                }
            }
            return next;
        }

  public static int KMP(string str, int slen, string ptr, int plen, int[] next)
        {
            int s_i = 0, p_i = 0;
            int count = 0;

            while (s_i < slen && p_i < plen)
            {
                ++count;
                if (str[s_i] == ptr[p_i])
                {
                    s_i++;
                    p_i++;
                }
                else
                {
                    if (p_i == 0)
                    {
                        s_i++;
                    }
                    else
                    {
                        p_i = next[p_i - 1] + 1;
                    }
                }
            }
            Console.WriteLine("数量：" + count);
            return (p_i == plen) ? (s_i - plen) : -1;
        }