831. KMP字符串 · znzryb

## 思路讲解

这个视频讲解还不错

[](https://www.bilibili.com/video/BV1AY4y157yL/?spm_id_from=333.337.search-card.all.click&vd_source=4350e5f2584d2f27c848b347ea11b675)

## AC代码

[https://www.acwing.com/problem/content/submission/code_detail/38373269/](https://www.acwing.com/problem/content/submission/code_detail/38373269/)

```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e5)+10,N2=1e6+10;
ll n,m;
char P[N],S[N2];
ll nxt[N];	// next数组

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>P+1>>m>>S+1;
	// nxt 递推
	for(int i=2,j=0;i<=n;++i){
		while (j && P[i]!=P[j+1]) 
			j=nxt[j];
		if(P[i]==P[j+1]) 
			++j;
		nxt[i]=j;
	}
	// kmp 匹配过程
	for(int i=1,j=0;i<=m;++i){
		while (j && S[i]!=P[j+1]) 
			j=nxt[j];
		if(S[i]==P[j+1])
			++j;
		if(j==n){
			cout<<i-j<<" ";
		}
	}
	cout<<"\n";
}
// AC https://www.acwing.com/problem/content/submission/code_detail/38373269/
```

## 心路历程（WA，TLE，MLE……）

自己写的，稍微有点问题

```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e5)+10,N2=1e6+10;
ll n,T,n2;
char P[N],S[N2];
ll nxt[N];	// next数组

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>P[i];
	}
	
	cin>>n2;
	for(int i=1;i<=n2;++i){
		cin>>S[i];
	}
	// nxt数组递推O（n）生成
	for(int i=2;i<=n;++i){
		if(P[i]==P[nxt[i-1]+1])
			nxt[i]=nxt[i-1]+1;
		else
			nxt[i]=0;
	}
	vector<ll> ans;
	for(int i=1,j=1;i<=n2;++i){
		if(S[i]==P[j]){
			if(j==n){
				ans.push_back(i-j);
				j=nxt[j-1]+2;
			}else{
				++j;
			}
		}else{
			if(i==n2)
				break;
			j=nxt[j-1]+2;
		}
	}
	for(int i=0;i<ans.size();++i)
		cout<<ans[i]<<" ";
	cout<<endl;
}
/*
3
aba
5
ababa

5
ABABC
7
ABABABC

2
ab
7
abcababc

3
aaa
10
aaaaaaabaa

*/
```