KMP算法实现字符串匹配
2024-01-02 19:28:25
方法一:暴力循环匹配
时间复杂度:O(n*m)
// 1.暴力匹配
class Solution {
public:
int strStr(string haystack, string needle) {
int index = 0;
for(auto i=haystack.begin(); i!=haystack.end(); i++){
auto pos = i;
auto j = needle.begin();
while(pos != haystack.end()){
if(*(pos++) != *(j++)){
break;
}
if(j == needle.end()){
return index;
}
}
index++;
}
return -1;
}
};
方法二:KMP匹配法
(当字符不匹配时,根据模板字符串的最长公共前后缀表next,回退至匹配位置;而不是从下一位置重新循环)详见代码注释。
时间复杂度:O(n+m)
// 2.KMP匹配
class Solution {
public:
// 根据模板字符串needle计算公共前后缀表next
void findNext(const string& needle, vector<int>& next ){
// 初始化next
int j = 0;
next[0] = j;
// 针对needel[0,i]的字符串:j指向前缀最后一个字符,i指向后缀最后一个字符
for(int i=1; i<needle.size(); i++){
// 前缀后缀不相等 -> j后退(直至找到相等前缀位置 or 初始位置0)
while( j>0 && needle[i]!=needle[j]){
j = next[j-1];
}
// 前缀后缀相等 -> i,j前进
if(needle[i] == needle[j]){
j++;
}
// 记录needle[0,i]字符串的最长公共前后缀的长度(即前缀最后一个字符指向位置j)
next[i] = j;
}
}
// KMP字符串匹配法
int KMP(const vector<int>& next, const string& haystack, const string& needle){
// i指向haystack,j指向needle
int j = 0;
for(int i=0; i<haystack.size(); i++){
// 不匹配->j根据next表后退至匹配位置
while( j>0 && haystack[i]!=needle[j]){
j = next[j-1];
}
// 匹配->i,j前进
if( haystack[i] == needle[j]){
j++;
}
//
if(j == needle.size()){
return (i-needle.size()+1);
}
}
return -1;
}
int strStr(string haystack, string needle) {
vector<int> next(needle.size());
// 计算模板字符串needle计算公共前后缀表next
findNext(needle, next);
// 根据next进行字符串匹配
int res = KMP(next, haystack, needle);
return res;
}
};
虽然我在力扣上运行两种方法的时间差不多。
文章来源:https://blog.csdn.net/qq_43855258/article/details/135344458
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!