1140：验证子串–next.data()、KMP和find

题目

解析

对于字符串的匹配常见的KMP算法【面试常考】 KMP中需要注意的是：应该从下标1开始遍历，因为下标0前面无值，不能匹配next 固在循环外应初始next[0]=0;//易忘点 next[0]=0;//易错点 //i需从1开始遍历，因为下标0前面无值，不能匹配next for(int i=1;i next(10); // 创建一个有10个int的数组 int* ptr = next.data(); // 获取底层数组的首地址

KMP代码

#include #include #include #include #include #include #include #include // 包含INT_MAX常量 #include #include using namespace std; void getNext(string s,int *next){ int j=0; next[0]=0; //i需从1开始遍历，因为下标0前面无值，不能匹配next for(int i=1;i0&&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; vectornext(s2.size()); getNext(s2,next.data()); int j=0; for(int i=0;i0&&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< #include #include #include using namespace std; const int N = 1e2 + 10; int a[N]; int cnt; int main() { string s1, s2; cin » s1 » s2; if (s1.length() > s2.length()) { if (s1.find(s2) != -1) cout « s2 « " is substring of " « s1; else cout « “No substring”; } //这里的else覆盖率长度相等的情况 else if (s2.find(s1) != -1) cout « s1 « " is substring of " « s2; else cout « “No substring”; }