恐怕现在用过电脑的人，一定都知道大部分带文本编辑功能的软件都有一个快捷键ctrl+f 吧（比如word）。这个功能主要来完成“查找”，“替换”和“全部替换”功能的，其实这就是典型的模式匹配的应用，即在文本文件中查找串。
1.模式匹配
模式匹配的模型大概是这样的：给定两个字符串变量S和P，其中S成为目标串，其中包含n个字符，P称为模式串，包含m个字符，其中m= 0)//迭代的过程
{
i = next[i];
}
if(str[j] == str[i+1])
{
next[j] = i+1;
}
else
{
next[j] = -1;
}
}
}
当前位置: 编程技术>c/c++/嵌入式
快速模式匹配算法(KMP)的深入理解
来源: 互联网 发布时间：2014-10-16
本文导语: 恐怕现在用过电脑的人，一定都知道大部分带文本编辑功能的软件都有一个快捷键ctrl+f 吧（比如word）。这个功能主要来完成“查找”，“替换”和“全部替换”功能的，其实这就是典型的模式匹配的应用，即在文本文件中查...
现在有了next数组保存的k值，就可以实现KMP算法了：
代码如下:
View Code
//des是目标串，pat是模式串，len1和len2是串的长度
int kmp(char des[],int len1,char pat[],int len2)
{
Next(str2,len2);
int p=0,s=0;
while(p < len2 && s < len1)
{
if(pat[p] == des[s])
{
p++;s++;
}
else
{
if(p==0)
{
s++;//若第一个字符就匹配失败，则从des的下一个字符开始
}
else
{
p = next[p-1]+1;//用失败函数确定pat应回溯到的字符
}
}
}
if(p < len2)//整个过程匹配失败
{
return -1;
}
return s-len2;
}
时间复杂度：
对于Next函数近似接近O（m），KMP算法的时间复杂度为O(n)，所以整个算法的时间复杂度为O(n+m)
空间复杂度：
多引入了O（m）的空间复杂度。
4.应用KMP的一道面试题
给定两个字符串是s1和s2，要判定s2是否能够被s1做循环移位得到的字符串包含。例如s1=AABCD，s2 =CDAA，返回true，因为s1循环移位可以变成CDAAB。给定s1=ACBD和s2=ACBD则返回false。
分析：不难发现对s2移位得到的字符串都将是字符串s1s1的子串，如果s2可以有s1循环移位得到，那么s2一定是s1s1的子串，这时KMP算法是不是就很管用了呢。
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术，将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外，均为转载、整理或搜集自网络。欢迎任何形式的转载，转载请注明出处。
本站(WWW.)站内文章除注明原创外，均为转载、整理或搜集自网络。欢迎任何形式的转载，转载请注明出处。