声明
本文主要是一些代码，加一些例题，基本为模板，仔细内容讲解会给出其他博主的链接
如果想要知道一个字符串是否在另一个字符串中出现过，那么首先想到的就是暴力枚举
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
string s1,s2;
int baolipipei() {
int len1=s1.size() ;
int len2=s2.size() ;
int i=0,j=0;
while(i<len1 && j<len2) {
if(s1[i]==s2[j]) {
i++;
j++;
}
else {
i=(i-j)+1;
j=0;
}
}
if(j==len2) return i-j;
return -1;
}
int main() {
cin>>s1>>s2;
cout<<baolipipei()<<endl;
}
但是，在两个字符串都很长的情况下，时间复杂度就很大，因此，给出一种算法KMP，可以解决字符串匹配等一类问题，在说KMP之前呢，首先说一下KMP用的一个数组，next数组（名字先不要在意）。next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。
那么如何求这个数组呢，暴力可以，但是复杂度过大
里面有详细的讲解，各位可以参考一下，主要还是理解之后大家记模板，也比较好记
https://blog.csdn.net/buppt/article/details/78531384
下面给出代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int maxn=1005;
string s;
int next[maxn];//最长前后缀相等
void GetNext() {
int i,j=-1;
next[0]=-1;//初始化为j=-1,next[0]=-1
for(int i=1;i<s.size() ;i++) {
while( j != -1 && s[i] != s[j+1] ) {//不断回退，直到j=-1，或者s1[i]=s2[j+1]
j=next[j];//next[j]=next[ next[i-1] ] ,next[i-1]=j
//牵扯到回溯，当时有点迷，所以写了上一行注释，希望能有帮助
}
if(s[i] == s[j+1]) {//匹配成功，令j++
j++;
}
next[i]=j;
}
}
int main() {
cin>>s;
GetNext();
for(int i=0;i<s.size() ;i++) {
cout<<next[i]<<" ";
}
}
现在呢开始进行匹配，我们知道，如果用暴力，当匹配到不正确的时候i会回到当前要查找的模式串（pattern）开头在对应的文本串（text）的位置下一位，那么根据next数组的含义，就可以直接回退到离当前j最近的j’使text[i] = pattern[j’+1] 能够成立。
这应该是博客上比较好的讲解kmp算法的了（可以看一看）：
https://blog.csdn.net/v_july_v/article/details/7041827
KMP算法的一般思路：
① 初始化j=-1，表示pattern当前已被匹配的最后位。
②让i遍历文本串text，对每个i，执行③，④来试图匹配text[i]和pattern[j+1]。
③不断令j=next[j],直到j回退到-1，或者text[i] = pattern[j+1] 成立。
④如果text[i] = pattern[j+1] ，令j++。如果j达到pattern模式串的长度-1,说明pattern是text的子串。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1005;
string s1,s2;
int next[maxn];
void GetNext() {//计算pattern的next数组
int i,j=-1;
next[0]=-1;
for(int i=1;i<s2.size() ;i++) {
while(j != -1 && s1[i] != s2[j+1] ) {
j = next[j];
}
if(s1[i] == s2[j+1]) {
j++;
}
next[i] = j;
}
}
bool KMP() {
GetNext();//计算pattern的next数组
int j=-1;//初始化j=-，表示还没有任意一位被匹配
for(int i=0;i<s1.size() ;i++) {
while(j != -1 && s1[i] != s2[j+1] ){
j=next[j];//一直回退，直到j=-1,或者s1[i]=s2[j+1]
}
if(s1[i] == s2[j+1] ) {
j++;//匹配成功，令j++
}
if(j == s2.size() -1) {
return true;//完全匹配时，返回true
}
}
return false;//循环结束，还未被匹配，返回false
}
int main() {
cin>>s1>>s2;
if(KMP()) {
cout<<"Yes\n";
}
else cout<<"No\n";
}
看到了求next数组和字符串匹配的代码后，发现他们惊人的相似，事实上：求解next数组的过程就是模式串自己匹配的过程。
接下来，怎么用KMP来统计子串出现的次数呢？
暴力的思路肯定还是回到开头，但是知道了上面的内容，我们回溯肯定就用next[j]了。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int maxn=1005;
int next[maxn];
string s1,s2;
void GetNext() {
int j=-1;
next[0]=-1;
for(int i=1;i<s2.size() ;i++) {
while(j!=-1 && s2[i]!=s2[j+1]) {
j=next[j];
}
if(s2[i]==s2[j+1]) {
j++;
}
next[i]=j;
}
}
int KMP() {
GetNext();//求出s2的next数组
int ans=0;
int j=-1;//初始化j=-1
for(int i=0;i<s1.size() ;i++) {
while(j != -1 && s1[i] != s2[j+1]){
j=next[j];//不断回退，直到j=-1，或者s1[i]=s2[j+1]
}
if(s1[i]==s2[j+1]) {
j++;//如果匹配成功，j++
}
if(j==s2.size() -1) {
ans++;//匹配完成，ans++;
j=next[j];//令j回退到上一个匹配位
}
}
return ans;
}
int main() {
cin>>s1>>s2;
cout<<KMP()<<endl;
}
next优化：
当next[j]表示的串的j+1位失配时，就要继续进行回退，那么如果还失配，同样的还要回退，我们最开始做next数组的意义不就是减少无用功吗?因此改变了一下next数组存放的内容，让失配时回退一次就行了。那么现在，我们把优化后的next数组几位nextvel数组，他失去了next数组的最长前后缀相等的含义，现可理解为当模式串pattern的i+1位失配时，i应该会退的最佳位置。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1005;
string s;
int nextvel[maxn];//nextvel[i]的含义应理解为当模式串的i+1完全失配时，i应当退回的最佳位置 j
void GetNextvel() {
int j=-1;
nextvel[0]=-1;
for(int i=1;i<s.size() ;i++) {
while(j!=-1&&s[i]!=s[j+1]) {
j=nextvel[j];
}
if(s[i]==s[j+1]) {
j++;
}
if(j==-1||s[i+1]!=s[j+1]) {//j=-1时，不用回退
nextvel[i]=j;//求next数组中只有这句
}
else nextvel[i]=nextvel[j];
}
}
int main() {
cin>>s;
for(int i=0;i<s.size() ;i++) {
cout<<nextvel[i]<<" ";
}
}
nextvel数组可以直接替换掉KMP中的next数组
直接套模板的几道题：
http://poj.org/problem?id=3461
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
const int maxn1=1e6+5;
const int maxn2=1e4+5;
char s2[maxn2],s1[maxn1];
int next[maxn2];
int len1,len2;
void GetNext() {
int j=-1;
next[0]=-1;
for(int i=1;i<len2 ;i++) {
while(j != -1 && s2[i] != s2[j+1]) {
j=next[j];
}
if(s2[i] == s2[j+1]) {
j++;
}
next[i]=j;
}
}
int KMP() {
GetNext();
int j=-1;
int ans=0;
for(int i=0;i< len1 ;i++) {
while(j!=-1&&s1[i]!=s2[j+1]) {
j=next[j];
}
if(s1[i]==s2[j+1]) {
j++;
}
if(j==len2 -1) {
ans++;
j=next[j];
}
}
return ans;
}
int main() {
int t;
scanf("%d",&t);
while(t--) {
scanf("%s%s",s2,s1);
len1=strlen(s1);
len2=strlen(s2);
printf("%d\n",KMP());
}
}
http://poj.org/problem?id=2752
这是直接利用next数组的题目，需要的就是最大前后缀，而next数组刚好有这个意思
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int maxn=400005;
int next[maxn];
int shu[maxn];
char s[maxn];
void GetNext(int len) {//求出每一位前缀后缀最大，用next记录
int j=-1;
next[0]=-1;
for(int i=1;i<len ;i++) {
while(j!=-1 && s[i]!=s[j+1]){
j=next[j];
}
if(s[i]==s[j+1]){
j++;
}
next[i]=j;
}
}
int main() {
while(~scanf("%s",s)) {
int len=strlen(s);
GetNext(len);
int ans=0;
shu[ans++]=len;
int j=len -1;
while(next[j]!=-1){
shu[ans++]=next[j]+1;
j=next[j];//在已经匹配的前j位中找最大的，依次进行下去，直到第一位，即next[0]=-1;
}
for(int i=ans-1;i>=0;i--){//反向输出
printf("%d",shu[i]);
if(i) printf(" ");
}
printf("\n");
}
}
http://caioj.cn/problem.php?id=1177
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>
using namespace std;
typedef long long LL;
const int maxn=1005;
int nextvel[maxn];
string s1,s2;
int len1,len2;
void GetNextvel() {
int j=-1;
nextvel[0]=-1;
for(int i=1;i<len2;i++) {
while(j!=-1&&s2[i]!=s2[j+1]) j=nextvel[j];
if(s2[i]==s2[j+1]) j++;
if(j==-1||s2[i+1]!=s2[j+1]) nextvel[i]=j;
else nextvel[i]=nextvel[j];
}
}
void KMP() {
GetNextvel();
int j=-1;
for(int i=0;i<len1;i++) {
while(j!=-1&&s1[i]!=s2[j+1]) j=nextvel[j];
if(s1[i]==s2[j+1]) j++;
if(j==len2-1) {
cout<<i-j+1<<" "<<i+1<<endl;
return;
}
}
cout<<"NO\n";
}
int main() {
cin>>s1>>s2;
len1=s1.size() ;
len2=s2.size() ;
KMP();
}
最后，其实我个人觉得一些算法模板直接记录下来，能够熟练的打下来也很厉害了（小声说）
![【NOIP2018模拟赛2018.10.3】track[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)