C# KMP算法字符串匹配

命题：设计算法，在字符串s中，从pos位置开始，查找第一个与目标字符串t相同的子字符串的起始位置。

kmp算法实现：第一步，预处理目标字符串t，求出t中每一个字符在与源字符串s中字符不等时移到的位置。方法是根据如下公式

next[0]=-1;
next[j]=max{k|0<k<j&&"t0t1...t(k-1)"=="t(j-k)t(j-k+1)...t(j-1)"};
next[j]=0;

此公式可如下证明

首先，假设目标字符串下一次移动到k位置，那么这个k位置有什么特性呢，k之前的所有字符（k个，从0开始），应该和源字符串s中i位置前的k个字符相同，即：

"t0t1...t（k－1）"=="s(i-k)s(i-k+1)...s(i-1)"

而且，这时候，源字符串i位置之前的k个字符和目标字符串j位置之前的k个字符也相同，即：

"t(j-k)t(j-k+1)...t(j-1)"=="s(i-k)s(i-k+1)...s(i-1)"

那么得到如下结论

"t0t1...t（k－1）"=="t(j-k)t(j-k+1)...t(j-1)"

第二步，循环源字符串和目标字符串，如下吧，这段不好说了

while(s[i] != ’’ && t[j] != ’’){if(j == -1 || s[i] == t[j]) //j==-1表示s[i]与t[0]不同{i++;j++;}else{j = next[j];}}if(t[j] == ’’)return i-j;elsereturn 0;

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索算法
， c#
， 字符串
， 位置
， 字符
目标
c站、c语言、cf、ch、c罗，以便于您获取更多的相关知识。