离谱的事情经过：

我开场掉进了SAM的粪坑里，想到了一个很好Hack的SAM上假贪心，然后居然只错了一个点？！

更离谱的：正着来一遍倒着再来一遍就过了？？！

小朋友你是否有许多问号

求hack，谢谢

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
char s[maxn],t[maxn];
int ch[maxn][2],len[maxn],link[maxn],sz,last;
void append(int x){
	int cur = ++sz,p = last;
	len[cur] = len[last] + 1;
	while(~p&&!ch[p][x])ch[p][x] = cur,p = link[p];
	if(p == -1)link[cur] = 0;
	else{
		int q = ch[p][x];
		if(len[q] == len[p] + 1)link[cur] = q;
		else{
			int nq = ++sz;
			len[nq] = len[p] + 1,link[nq] = link[q],link[q] = link[cur] = nq,memcpy(ch[nq],ch[q],8);
			while(~p&&ch[p][x]==q)ch[p][x] = nq,p = link[p];
		}
	}
	last = cur;
} 
int maxl[maxn];
int getlen(int x){
	if(maxl[x] != -1)return maxl[x];
	int &res = maxl[x];res = 0;
	for(int i=0;i<2;++i)
		if(ch[x][i])
			res = max(res,getlen(ch[x][i])+1);
	return res;
}
int main(){
	scanf("%s",s);
	scanf("%s",t);
	link[sz=last=0] = -1;
	for(int i=0;s[i];++i)append(s[i]-'0');
	for(int i=0;i<=sz;++i)maxl[i] = -1;
	getlen(0);
	int now = 0,Len = strlen(t),ans=0;
	for(int i=0;i<Len;++i){
		if(!ch[now][t[i]-'0'] || maxl[ch[now][t[i]-'0']] < Len-i-1)
			++ans,now = ch[now][(t[i]-'0')^1];
		else now = ch[now][t[i]-'0'];
	}
	memset(ch,0,sizeof(ch)),memset(link,0,sizeof(link)),memset(len,0,sizeof(len));
	link[sz=last=0] = -1;
	int LLen = strlen(s);
	for(int i=LLen-1;~i;--i)append(s[i]-'0');
	for(int i=0;i<=sz;++i)maxl[i] = -1;
	getlen(0);
	now = 0,Len = strlen(t);
	int ans2=0;
	for(int i=Len-1;~i;--i){
		if(!ch[now][t[i]-'0'] || maxl[ch[now][t[i]-'0']] < i)
			++ans2,now = ch[now][(t[i]-'0')^1];
		else now = ch[now][t[i]-'0'];
	}
	printf("%d",min(ans,ans2));
	return 0;
}