C# KMP算法字符串匹配
2010-03-04 12:06:08 来源:WEB开发网核心提示:命题:设计算法,在字符串s中,C# KMP算法字符串匹配,从pos位置开始,查找第一个与目标字符串t相同的子字符串的起始位置,即:"t(j-k)t(j-k+1)...t(j-1)"=="s(i-k)s(i-k+1)...s(i-1)"那么得到如下结论"t0t1...t(
命题:设计算法,在字符串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]==’’)
returni-j;
else
return0;
- ››字符串分割
- ››字符串格式化工具
- ››算法大全(3) 二叉树
- ››KMP模式匹配算法分析与实现
- ››KMP算法的Java实现例子以及测试分析
- ››KMPlayer也能复制加密VCD影碟
- ››算法
- ››字符串近似匹配算法
- ››KMPlayer源代码早被潘多拉TV收购
- ››字符串分割的两种方法
- ››字符串类数据列类型(参考)
- ››字符串的一些操作
更多精彩
赞助商链接