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#程序设计有所帮助。
-
本文向大家介绍python实现kmp算法的实例代码，包括了python实现kmp算法的实例代码的使用技巧和注意事项，需要的朋友参考一下 kmp算法 kmp算法用于字符串的模式匹配，也就是找到模式字符串在目标字符串的第一次出现的位置 比如 abababc 那么bab在其位置1处，bc在其位置5处 我们首先想到的最简单的办法就是蛮力的一个字符一个字符的匹配，但那样的时间复杂度会是O(m*n) kmp算
-
本文向大家介绍C语言实现字符串匹配KMP算法，包括了C语言实现字符串匹配KMP算法的使用技巧和注意事项，需要的朋友参考一下 字符串匹配是计算机的基本任务之一。 举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？ 下面的的KMP算法的解释步骤 1. 首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符
-
本文向大家介绍扩展KMP算法(Extend KMP)，包括了扩展KMP算法(Extend KMP)的使用技巧和注意事项，需要的朋友参考一下 扩展kmp既是求模式串和主串的每一个后缀的最长公共前缀 即令s[i]表示主串中以第i个位置为起始的后缀，则B[i]表示s[i]和模式串的最长公共前缀 显然KMP是求s[i]=模式串长度的情况，所以，扩展KMP是对KMP的拓展 像求KMP的next数组一样，我们
-
本文向大家介绍Python实现字符串匹配的KMP算法，包括了Python实现字符串匹配的KMP算法的使用技巧和注意事项，需要的朋友参考一下 kmp算法 KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达
-
本文向大家介绍KMP 算法实例详解，包括了KMP 算法实例详解的使用技巧和注意事项，需要的朋友参考一下 KMP 算法实例详解 KMP算法，是由Knuth，Morris，Pratt共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。 分析：KMP模板题、KMP的关键是求出next的值、先预处理出next的值、然后一遍扫过、复
-
本文向大家介绍详解KMP算法以及python如何实现，包括了详解KMP算法以及python如何实现的使用技巧和注意事项，需要的朋友参考一下 算法思路 Knuth-Morris-Pratt（KMP）算法是解决字符串匹配问题的经典算法，下面通过一个例子来演示一下： 给定字符串"BBC ABCDAB ABCDABCDABDE"，检查里面是否包含另一个字符串"ABCDABD"。 1.从头开始依次匹配字符，