KMP算法的C#实现方法

本文实例简述了KMP算法的C#实现方法，分享给大家供大家参考。具体如下：

具体思路为：next函数求出模式串向右滑动位数，再将模式串的str的next函数值 存入数组next。

具体实现代码如下：

static void GetNextVal(string str, int [] next)
{
  int i = 0;
  int j = -1;
  next[0] = -1;
  while (i < str.Length - 1)
  {
 if (j == -1 || str[i] == str[j])
 {
   i++;
   j++;
   next[i] = j;
 }
 else
 {
   j = next[j];
 }
  }
}

KMP算法代码如下：

static int KMP(string zstr, string mstr)
{
  int i, j;
  int[] next = new int[mstr.Length];
  GetNextVal(mstr, next);
  i = 0;
  j = 0;
  while (i < zstr.Length && j < mstr.Length)
  {
 if (j == -1 || zstr[i] == mstr[j])
 {
   ++i;
   ++j;
 }
 else
 {
   j = next[j];
 }
  }
  if (j == mstr.Length)
 return i - mstr.Length;
  return -1;
}


static void Main(string[] args)
{
  string zstr, mstr;
  zstr = Console.ReadLine();
  mstr = Console.ReadLine();
  int pos1;
  pos1 = KMP(zstr, mstr);
  if (pos1 == -1) Console.WriteLine("没有匹配的字符串！");
  else Console.WriteLine(pos1);
  Console.Write("请按任意键继续。。");
  Console.ReadKey(true);
}
}

希望本文所述对大家的C#程序设计有所帮助。