KMP算法的C#实现方法 KMP算法的C#实现方法

时间:2021-03-19 人气:0

想了解KMP算法的C#实现方法的相关内容吗，在本文为您仔细讲解KMP算法的C#实现方法的相关知识和一些Code实例，欢迎阅读和指正，我们先划重点：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#程序设计有所帮助。

加载全部内容