P3375 【模板】KMP

https://www.luogu.com.cn/problem/P3375

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
vector<int> get_pi(string s){
	int n=s.length();
	vector<int> pi(n);
	for(int i=1;i<n;++i){
		int j=pi[i-1];
		while(j&&s[i]-s[j])j=pi[j-1];
		if(s[i]==s[j])j++;
		pi[i]=j;
	}
	return pi;
}
string s,sl;
vector<int> get_id(string text,string pattern){
	string cur=pattern+'#'+text;
	int lent=text.size(),lens=pattern.size();
	vector<int> v;
	vector<int> lps=get_pi(cur);
	for(int i=lens+1;i<=lent+lens;++i){
		if(lps[i]==lens)v.push_back(i-2*lens);
	}
	return v;
}
int main(){
	cin>>s>>sl;
	vector<int> id=get_id(s,sl);
	for(int i=0;i<(int)id.size();++i)printf("%d\n",id[i]+1);
	vector<int> st=get_pi(sl);
	for(int i=0;i<st.size();++i)printf("%d ",st[i]);
	return 0;
}