串串选做

KMP

OI-wiki上有一个很不错的kmp做法，就是直接把模式串与文本串用特殊符号链接，然后求前缀数组即可
感觉vector可能更舒服(?)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

const int N=2000000;
char a[N],b[N];
vector<char>c;
vector<int>kmp;

void solve(){
	scanf("%s%s",a,b);
	int la=strlen(a),lb=strlen(b);
	for(int i=0;i<lb;++i) c.push_back(b[i]);
	c.push_back('\0');
	for(int i=0;i<la;++i) c.push_back(a[i]);
	kmp.push_back(0);
	for(int i=1;i<=la+lb;++i){
		int j=kmp[i-1];
		while(j>0&&c[i]!=c[j]) j=kmp[j-1];
		if(c[i]==c[j]) kmp.push_back(j+1);
		else kmp.push_back(j);
		if(kmp[i]==lb) printf("%d\n",i-2*lb+1);
	}
	for(int i=0;i<lb;++i) printf("%d ",kmp[i]);
}

int main(){
	solve();
	return 0;
}