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#程序设计有所帮助。