613E - Puzzle Lover - CodeForces Solution

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define Rof(i,b,a) for(int i=(b),i##END=(a);i>=i##END;i--)
#define go(u) for(int i=head[u];i;i=nxt[i])
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=2e3+10,base=131,p=1e9+7;
int n,len,ans;char s[2][N],w[N];
int h1[2][N],h2[2][N],H[N],pw[N];
int getz(int *h,int l,int r){assert(l<=r);return (h[r]-h[l-1]*pw[r-l+1]%p+p)%p;}
int getf(int *h,int r,int l){assert(l<=r);return (h[l]-h[r+1]*pw[r-l+1]%p+p)%p;}
int f[2][N][N],g[2][N][N];
void solve(){
	For(i,0,1)For(j,1,n)h1[i][j]=(h1[i][j-1]*base+s[i][j])%p;
	For(i,0,1)Rof(j,n,1)h2[i][j]=(h2[i][j+1]*base+s[i][j])%p;
	For(i,1,len)H[i]=(H[i-1]*base+w[i])%p;
	memset(f,0,sizeof f),memset(g,0,sizeof g);
	For(j,1,n){
		For(i,0,1){
			if(s[i][j]==w[1])g[i][j][1]++;
			For(k,1,min(j,len/2))
				if(getf(h2[i^1],j,j-k+1)==getz(H,1,k)&&getz(h1[i],j-k+1,j)==getz(H,k+1,2*k))g[i][j][2*k]++;
		}
		For(i,0,1)For(k,1,min(2*j,len-1))
			if(s[i^1][j]==w[k+1])(g[i^1][j][k+1]+=f[i][j][k])%=p;
		For(i,0,1)For(k,1,min(2*j,len-1)){
			if(s[i][j+1]==w[k+1])(f[i][j+1][k+1]+=g[i][j][k]+f[i][j][k])%=p;
		}
	}
	For(i,0,1)For(j,1,n)For(k,1,min(2*j,len)){
		int v=(f[i][j][k]+g[i][j][k])%p;if(!v)continue;
		if(k+1==len&&s[i][j+1]==w[len])(ans+=v)%=p;
		if((len-k)%2==0&&k<len){
			int o=(len-k)/2;if(j+o>n)continue;
			if(getz(h1[i],j+1,j+o)==getz(H,k+1,k+o)&&getf(h2[i^1],j+o,j+1)==getz(H,len-o+1,len)){
				(ans+=v)%=p;
			}
		}
	}
	if(len%2==0){
		int o=len/2;
		For(i,0,1)For(j,1,n-o+1){
			if(getz(h1[i],j,j+o-1)==getz(H,1,o)&&getf(h2[i^1],j+o-1,j)==getz(H,o+1,len))ans++;
		}
	}
}
signed main(){
	pw[0]=1;For(i,1,2000)pw[i]=pw[i-1]*base%p;
	scanf("%s%s%s",s[0]+1,s[1]+1,w+1);
	n=strlen(s[0]+1),len=strlen(w+1);
	if(len==1){
		For(i,0,1)For(j,1,n)ans+=s[i][j]==w[1];
		return printf("%lld\n",ans),0;
	}
	if(len==2){
		For(i,0,1)For(j,1,n-1)ans+=s[i][j]==w[1]&&s[i][j+1]==w[2];
		For(i,0,1)For(j,1,n-1)ans+=s[i][j]==w[2]&&s[i][j+1]==w[1];
		For(j,1,n)ans+=s[0][j]==w[1]&&s[1][j]==w[2];
		For(j,1,n)ans+=s[0][j]==w[2]&&s[1][j]==w[1];
		return printf("%lld\n",ans),0;
	}
	solve();
	For(i,0,1)reverse(s[i]+1,s[i]+n+1);solve();
	printf("%lld\n",ans);
	return 0;
}

/*
aaaaa
aaaaa

aaaaa

96
*/