KMP——总结

KMP文章

1140：验证子串–next.data()、KMP和find
459. 重复的子字符串【力扣】——kmp
28.找出字符串中第一个匹配项的下标【力扣】KMP前缀表 ≈ find() 函数、暴力解法

KMP模板

class Solution {
public:void getNext(string s,int *next){int j=0;//i需从1开始遍历，因为下标0前面无值，不能匹配next//易与下述遍历中的i初值混淆for(int i=1;i<s.size();i++){while(j>0&&s[i]!=s[j]) j=next[j-1];if(s[i]==s[j]) j++;next[i]=j;}}int strStr(string haystack, string needle) {vector<int> next(needle.size(),0);getNext(needle,next.data());int j=0;//注意！！！这里i初始值为0【易混淆写成1】//这是遍历比较，一个都不能放过for(int i=0;i<haystack.size();i++){while(j>0&&haystack[i]!=needle[j]) j=next[j-1];if(haystack[i]==needle[j]) j++;if(j==needle.size()) return i-needle.size()+1;}return -1;}
};

1140：验证子串

KMP代码

#include <iostream>
#include <vector>
#include<set>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
#include<map>
using namespace std;void getNext(string s,int *next){int j=0;next[0]=0;
//i需从1开始遍历，因为下标0前面无值，不能匹配nextfor(int i=1;i<s.size();i++){while(j>0&&s[i]!=s[j]) j=next[j-1];if(s[i]==s[j]) j++;next[i]=j;}
}bool check(string s1,string s2){if(s2.size()==0) return true;vector<int>next(s2.size());getNext(s2,next.data());int j=0;for(int i=0;i<s1.size();i++){while(j>0&&s1[i]!=s2[j]) j=next[j-1];if(s1[i]==s2[j]) j++;if(j==s2.size()) return true;}return false;
}
int main(){string s1,s2;cin>>s1>>s2;if(check(s2,s1)){cout<<s1 << " is substring of " << s2 << endl;return 0;}if(check(s1,s2)){cout<< s2 << " is substring of " << s1 << endl;return 0;}cout<<"No substring" << endl;
return 0;
}

find代码

#include <iostream>
#include <vector>
#include<set>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
#include<map>
using namespace std;int main(){
string s1,s2;
cin>>s1>>s2;
if(s1.size()>s2.size()){if(s1.find(s2)!=-1) cout << s2 << " is substring of " << s1;else cout << "No substring";
}
else{if(s2.find(s1)!=-1) cout<<s1<< " is substring of " << s2;else cout << "No substring";
}
return 0;
}

459. 重复的子字符串【力扣】

KMP代码

#include <iostream>
#include <vector>
#include<set>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
#include<map>
using namespace std;void getNext(string s,int *next){int j=0;for(int i=1;i<s.size();i++){while(j>0&&s[i]!=s[j]) j=next[j-1];if(s[i]==s[j]) j++;next[i]=j;}
}int main(){string s; cin>>s;vector<int> next(s.size(),0);getNext(s,next.data());if(s.size()%(s.size()-next[s.size()-1])==0) cout<<"true";else cout<<"false";
return 0;
}

find代码

#include <iostream>
#include <vector>
#include<set>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
#include<map>
using namespace std;
string s; 
int main(){cin>>s;(s+s).find(s,1)!=s.size()?cout<<true:cout<<false;return 0;
}

28.找出字符串中第一个匹配项的下标【力扣】

KMP代码

class Solution {
public:
void getNext(string s,int *next){
int j=0;
for(int i=1;i<s.size();i++){
while(j>0&&s[i]!=s[j]) j=next[j-1];
if(s[i]==s[j]) j++;
next[i]=j;
}
}
int strStr(string haystack, string needle) {
vector next(needle.size(),0);
getNext(needle,next.data());
int j=0;
for(int i=0;i<haystack.size();i++){
while(j>0&&haystack[i]!=needle[j]) j=next[j-1];
if(haystack[i]needle[j]) j++;
if(jneedle.size()) return i-needle.size()+1;
}
return -1;
}
};

Find代码

class Solution {
public:int strStr(string haystack, string needle) {if(haystack.find(needle)!=-1) return haystack.find(needle);else return -1;}
};