KMP算法实现（C#）

//返回模式字符串对应的next值
static int[] Next(string T)
{
  //string str = "aaaab";//"ababcabababc";
  int[] next = new int[T.Length];

  //指引被对比字符串
  int i = 0;

  //指引模式字符串
  int j = -1;

  next[0] = -1;

  while (i < T.Length - 1)
  {
    if (j == -1 || T[i] == T[j])
    {
      i++;
      j++;

      if (i > 0)
      {
        next[i] = j;
      }
    }
    else
    {
      j = next[j];
    }
  }
	//优化next数组
  for (int m = 0; m < next.Length; m++)
  {
    int k = next[m];
    if (next[m] == -1)
      continue;

    if (T[m] == T[k])
    {
      next[m] = next[k];
    }
  }
  
  return next;
}

//KMP算法本体
private static int KMP(string S,string T)
{
  //string S = "ababcabcaabcbaabc";
  //string strT = "cabc";//"ababcabababc";
  int[] next = Next(T);

  //指引被对比字符串
  int i = 0;

  //指引模式字符串
  int j = -1;
  

  while (i < S.Length)
  {
    if (j == -1 || S[i] == T[j])
    {
      i++;
      j++;

      if (j > T.Length - 1)
      {
        return i-j;
      }
    }
    else
    {
      j = next[j];
    }
  }

  return -1;
}



static void Main(string[] args)
{
  //int[] nextMain = Next();
  //foreach (int temp in nextMain)
  //{
  //  Console.Write(temp + " ");
  //}
  //Console.ReadKey();

  Console.WriteLine(KMP("ababcabcaabcbaabc", "cabc"));

  Console.ReadKey();
}

next()函数的意义：
1.找到模式字符串的当前字符前有几个字符与模式字符串开头字符相同