這題本質(zhì)上還是數(shù)據(jù)結(jié)構(gòu)。

首先看到這個(gè)$2\times n$的網(wǎng)格圖就很容易想到分治。我們還是考慮把要統(tǒng)計(jì)的東西變得可視化，一條路徑要么穿過中線一次，那么我們可以將兩邊的串拼起來得到答案；要么穿過中線兩次，考慮其中一邊的路徑是固定的，那么我們枚舉兩個(gè)端點(diǎn)再判斷一下和原串是否匹配的上就做完了。那么考慮預(yù)處理出$d{p}_{i,j,0/1,0/1}$表示從位置$(1/2,i)$開始，匹配長(zhǎng)度為$j$，向左/右走的方案數(shù)，這事實(shí)上非常好轉(zhuǎn)移，可以自己編一下。當(dāng)然可能還要把串正著和倒著處理一邊，總之挺麻煩的。

將網(wǎng)格圖翻轉(zhuǎn)后做兩次即可得到答案。求$Lcp$可以用暴力$dp$代替。事實(shí)上也并不需要分治。注意不要算重。

細(xì)節(jié)題，賊容易寫掛。

復(fù)雜度$O(n^2)$。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
#define db double
#define cpx complex<db>
using namespace std;
const int mod=1e9+7;
const int N=2005;
int n,K,Right[2][N][N],Left[2][N][N],dpl[2][N][N],res;
string s[2],str;
void add(int &x,int y){x=(x+y)%mod;
}
void solve(){for(int i=0;i<2;i++){for(int j=n-1;j>=0;j--){for(int k=0;k<K;k++){Right[i][j][k]=(s[i][j]!=str[k])?0:((j!=n-1&&k>=1)?(Right[i][j+1][k-1]+1):1);}}}for(int i=0;i<2;i++){for(int j=0;j<n;j++){for(int k=0;k<K;k++){Left[i][j][k]=(s[i][j]!=str[k])?0:((j>=1&&k>=1)?(Left[i][j-1][k-1]+1):1);}}}memset(dpl,0,sizeof dpl);for(int i=0;i<2;i++){for(int j=0;j<n;j++){if(s[i][j]==str[0]){dpl[i][j][0]=1;}}}//fixedfor(int i=0;i<n;i++){for(int j=i;j<n;j++){for(int k=0;k<2;k++){//strangeif(Left[k][j][2*(j-i+1)-1]>=j-i+1&&Right[k^1][i][j-i]>=j-i+1){add(dpl[k][j][2*(j-i+1)-1],1);}}}}for(int k=1;k<K;k++){for(int i=0;i<2;i++){for(int j=0;j<n;j++){if(s[i][j]==str[k]){if(j)add(dpl[i][j][k],dpl[i][j-1][k-1]);if(s[i^1][j]==str[k-1]){if(j&&k-2>=0)add(dpl[i][j][k],dpl[i^1][j-1][k-2]);}}}}}
}
void getans(){//fixedfor(int i=0;i<2;i++){for(int j=0;j<n;j++){add(res,dpl[i][j][K-1]);}}for(int i=1;i<n;i++){for(int j=i+1;j<n;j++){for(int k=0;k<2;k++){if(Right[k][i][K-1]>=j-i+1&&K-(j-i+2)>=0&&Left[k^1][j][K-(j-i+2)]>=j-i+1&&K-2*(j-i+1)-1>=0){add(res,dpl[k^1][i-1][K-2*(j-i+1)-1]);}}}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>s[0]>>s[1]>>str,n=s[0].size(),K=str.size();//fixedif(K==1){for(int i=0;i<2;i++){for(int j=0;j<n;j++){if(s[i][j]==str[0]){add(res,1);}}}cout<<res;return 0;}if(K==2){for(int i=0;i<2;i++){for(int j=0;j<n-1;j++){if(s[i][j]==str[0]&&s[i][j+1]==str[1]){add(res,1);}if(s[i][j+1]==str[0]&&s[i][j]==str[1]){add(res,1);}}}for(int i=0;i<2;i++){for(int j=0;j<n;j++){if(s[i][j]==str[0]&&s[i^1][j]==str[1]){add(res,1);}}}cout<<res;return 0;}//fixedsolve();getans();//fixedswap(s[0],s[1]),reverse(s[0].begin(),s[0].end()),reverse(s[1].begin(),s[1].end());solve();getans();cout<<res<<"\n";
}