以0为起点算的字符串

#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define __for(i,a,b) for(int i=a;i>=b;i--)
typedef unsigned long long ull;
using namespace std;
const int maxn=1e5;
int main(){
	int next[maxn+10];
	string s1,s2;
	cin>>s1>>s2;
	if(s1.length()<s2.length())swap(s1,s2);
	//求next数组 
	memset(next,0,sizeof(next));
	next[0]=0;next[1]=0;
	int j=0;
	_for(i,2,s2.length()-1){//计算第i位的最长相同前后缀 
		while(j&&s2[i]!=s2[j])j=next[j];//若无法匹配则往前找，除非找到头 
		if(s2[i]==s2[j]) next[i]=j++;//找到了 
		else next[i]=0;//找到头也找不到 
	}
	
	//匹配
	j=0;
	_for(i,0,s1.length()-1){
		while(j&&s1[i]!=s2[j]) j=next[j];//不匹配则前移 
		if(s1[i]==s2[j])j++;//能够匹配则继续匹配下一位
		if(j==s2.length()) printf("%d\n",i-s2.length()+2),j=next[j]+1;
	}
	
	//next 
	_for(i,0,s2.length()-1)printf("%d ",i>1?next[i]+1:next[i]);
	putchar('\n');
	
	return 0;
}