考场上想分情况讨论+记忆化搜索，但情况有点多讨论不起
发现蛇的走法一定是这样（题解）：
- 往回走 \(a\) 步（\(a\) 可以为 0），走到另一行，再向前走 \(a\) 步
- 上下扭动着往前走
- 向前走 \(b\) 步（\(b\) 可以为 0），走到另一行，再往回走 \(b\) 步
用hash预处理情况13，dp情况2就行了，但细节真的多我从下午2点写到早晨9点
Code:
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 2010
#define ll long long
#define ull unsigned long long
//#define int long long
int n, m;
char mp[3][N], s[N];
const ll p=1e9+7, base=131;
const int dlt[][2]={{-1,0},{1,0},{0,1},{0,-1}};
namespace force{
bool vis[3][N];
ll ans;
void dfs(int x, int y, int back, int pos) {
//cout<<"dfs "<<x<<' '<<y<<' '<<back<<' '<<pos<<endl;
if (pos==m) {++ans; return ;}
vis[x][y]=1;
for (int i=0,x2,y2; i<4; ++i) if (i!=back) {
x2=x+dlt[i][0], y2=y+dlt[i][1];
if (x2>=1&&x2<=2&&y2>=1&&y2<=n&&mp[x2][y2]==s[pos+1]&&!vis[x2][y2])
dfs(x2, y2, i^1, pos+1);
}
vis[x][y]=0;
}
void solve() {
for (int i=1; i<=2; ++i)
for (int j=1; j<=n; ++j)
if (mp[i][j]==s[1]) dfs(i, j, 4, 1); //, cout<<"return "<<endl;
printf("%lld\n", ans%p);
exit(0);
}
}
namespace task{
ll dp[2][N][N][2]; short hd[2][N][N], tail[2][N][N];
ull sh[N], h[3][N], b[N];
inline ull hashing(ull* h, int l, int r) {return h[r]-h[l-1]*b[r-l+1];}
ll solve(bool op) {
//cout<<double(sizeof(dp)+sizeof(hd))/1024/1024<<endl;
memset(dp, 0, sizeof(dp));
memset(hd, 0, sizeof(hd));
memset(tail, 0, sizeof(tail));
b[0]=1; ll ans=0;
for (int i=1; i<=n; ++i) b[i]=b[i-1]*base;
for (int i=1; i<=m; ++i) sh[i]=sh[i-1]*base+s[i];
for (int i=1; i<=n; ++i) h[1][i]=h[1][i-1]*base+mp[1][i];
for (int i=1; i<=n; ++i) h[2][i]=h[2][i-1]*base+mp[2][i];
for (int i=1; i<=n; ++i) if (mp[1][i]==s[1]) {
++dp[0][i][1][0];
for (int j=i-1; j&&mp[1][j]==s[i-j+1]; --j)
if (hashing(h[2], j, i)==hashing(sh, i-j+2, 2*i-2*j+2)) {
if (2*i-2*j+2==m && (m!=2||op)) ++ans;
else if (i<n && mp[2][i+1]==s[2*i-2*j+3]) {
++dp[1][i+1][2*i-2*j+3][0]; //, cout<<"1: "<<i<<' '<<j<<endl;
++tail[1][i][2*i-2*j+2];
}
}
}
for (int i=1; i<=n; ++i) if (mp[2][i]==s[1]) {
++dp[1][i][1][0];
for (int j=i-1; j&&mp[2][j]==s[i-j+1]; --j)
if (hashing(h[1], j, i)==hashing(sh, i-j+2, 2*i-2*j+2)) {
if (2*i-2*j+2==m && (m!=2||op)) ++ans;
else if (i<n && mp[1][i+1]==s[2*i-2*j+3]) {
++dp[0][i+1][2*i-2*j+3][0]; //, cout<<"2: "<<i<<' '<<j<<endl;
++tail[0][i][2*i-2*j+2];
}
}
}
for (int i=1; i<=n; ++i) if (mp[1][i]==s[m]) {
//cout<<"i: "<<i<<' '<<mp[1][i]<<' '<<s[m]<<endl;
for (int j=i+1; j<=n&&mp[1][j]==s[m-j+i]; ++j) {
//cout<<"j: "<<mp[1][j]<<' '<<s[m-j+i]<<endl;
//cout<<i<<' '<<j<<' '<<m-2*j+2*i-1<<' '<<m-j+i-1<<endl;
//cout<<hashing(h[2], i, j)<<' '<<hashing(sh, m-2*j+2*i-1, m-j+i-1)<<endl;
if (hashing(h[2], i, j)==hashing(sh, m-2*j+2*i-1, m-j+i-1)) {
//cout<<"check: "<<mp[2][i-1]<<' '<<s[m-2*j+2*i-2]<<' '<<m-2*j+2*i-1<<endl;
if (2*j-2*i+2==m && (m!=2||op)) ; //cout<<"error1"<<endl;
else if (i>1 && mp[2][i-1]==s[m-2*j+2*i-2])
++hd[1][i-1][m-2*j+2*i-2]; //, cout<<3<<' '<<i<<' '<<j<<endl;
}
}
}
for (int i=1; i<=n; ++i) if (mp[2][i]==s[m]) {
//cout<<"i: "<<mp[2][i]<<' '<<s[m]<<endl;
for (int j=i+1; j<=n&&mp[2][j]==s[m-j+i]; ++j) {
//cout<<"j: "<<mp[2][j]<<' '<<s[m-j+i]<<endl;
//cout<<hashing(h[1], i, j)<<' '<<hashing(sh, m-2*j+2*i-1, m-j+i-1)<<endl;
//cout<<i<<' '<<j<<' '<<m-2*j+2*i-1<<' '<<m-j+i-1<<endl;
if (hashing(h[1], i, j)==hashing(sh, m-2*j+2*i-1, m-j+i-1)) {
//cout<<"hash accepted "<<' '<<i<<' '<<mp[1][i-1]<<' '<<s[m-2*j+2*i-2]<<endl;
if (2*j-2*i+2==m && (m!=2||op)) ; //cout<<"error2"<<endl;
else if (i>1 && mp[1][i-1]==s[m-2*j+2*i-2])
++hd[0][i-1][m-2*j+2*i-2]; //, cout<<4<<' '<<i<<' '<<j<<endl;
}
}
}
//cout<<"ans: "<<ans<<endl;
#if 0
cout<<"ans: "<<ans<<endl;
for (int i=1; i<=n; ++i) cout<<dp[0][i]<<' '; cout<<endl;
for (int i=1; i<=n; ++i) cout<<dp[1][i]<<' '; cout<<endl;
for (int i=1; i<=n; ++i) {
cout<<dp[0][i]<<' ';
for (int j=1; j<=m; ++j) cout<<dp[0][i][j][0]<<' '; cout<<endl;
}
for (int i=1; i<=n; ++i) {
cout<<dp[1][i]<<' ';
for (int j=1; j<=m; ++j) cout<<dp[1][i][j][0]<<' '; cout<<endl;
}
#endif
for (int j=1; j<=n; ++j)
for (int k=1; k<=m; ++k) {
dp[0][j][k][1]=dp[0][j][k][0];
dp[1][j][k][1]=dp[1][j][k][0];
}
for (int j=1; j<=n; ++j) {
for (int k=1; k<=m; ++k) {
#if 0
printf("dp[%d][%d][%d][%d]=%lld\n", 1, j, k, 0, dp[0][j][k][0]);
printf("dp[%d][%d][%d][%d]=%lld\n", 1, j, k, 1, dp[0][j][k][1]);
printf("dp[%d][%d][%d][%d]=%lld\n", 2, j, k, 0, dp[1][j][k][0]);
printf("dp[%d][%d][%d][%d]=%lld\n", 2, j, k, 1, dp[1][j][k][1]);
//cout<<"now ans="<<ans<<endl;
#endif
if (mp[1][j]==s[k]) {
if ((m>2||op) && mp[2][j]==s[k+1]) dp[1][j][k+1][1]=(dp[1][j][k+1][1]+dp[0][j][k][0])%p;
if (mp[1][j+1]==s[k+1]) {
dp[0][j+1][k+1][1]=(dp[0][j+1][k+1][1]+dp[0][j][k][1])%p;
dp[0][j+1][k+1][0]=(dp[0][j+1][k+1][0]+dp[0][j][k][1])%p;
}
}
if (mp[2][j]==s[k]) {
if ((m>2||op) && mp[1][j]==s[k+1]) dp[0][j][k+1][1]=(dp[0][j][k+1][1]+dp[1][j][k][0])%p;
if (mp[2][j+1]==s[k+1]) {
dp[1][j+1][k+1][1]=(dp[1][j+1][k+1][1]+dp[1][j][k][1])%p;
dp[1][j+1][k+1][0]=(dp[1][j+1][k+1][0]+dp[1][j][k][1])%p;
}
}
ans=(ans+dp[0][j][k][1]*hd[0][j][k]+dp[1][j][k][1]*hd[1][j][k])%p;
//printf("able hd: %lld %lld\n", hd[0][j][k], hd[1][j][k]);
//printf("add hd: %lld %lld\n", dp[0][j][k][1]*hd[0][j][k], dp[1][j][k][1]*hd[1][j][k]);
ans=(ans+tail[0][j][k]*hd[0][j][k]+tail[1][j][k]*hd[1][j][k])%p;
}
ans=(ans+dp[0][j][m][1]+dp[1][j][m][1])%p;
//printf("add: %lld %lld\n", dp[0][j][m][1], dp[1][j][m][1]);
}
return ans;
}
}
signed main()
{
scanf("%s%s%s", mp[1]+1, mp[2]+1, s+1);
n=strlen(mp[1]+1); m=strlen(s+1);
//force::solve();
ll ans=task::solve(1);
//cout<<"first iterator: "<<ans<<endl;
reverse(mp[1]+1, mp[1]+n+1);
reverse(mp[2]+1, mp[2]+n+1);
printf("%lld\n", (ans+(m!=1?task::solve(0):0))%p);
return 0;
}