题意：给n*m的地图，在地图的点上走，(n+1)*(m+1)个点，两种操作：往下走D和往右走R。现在要从左上角走到右下角，给定两个操作串，问包含这两个串的走法总共有多少种。
做法：用这两个串构建自动机，然后只要在自动机上走n+m+1步就好了。就像一个递推，dp[x][y][i][cur]表示在i状态到达x，y坐标时走过的串的状态为cur时的总方案数
//#pragma comment(linker, "/STACK:102400000") #include<cstdlib> #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<set> #include<map> #include<list> #include<queue> #include<vector> #define tree int o,int l,int r #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define lo o<<1 #define ro o<<1|1 #define ULL unsigned long long #define LL long long #define inf 0x7fffffff #define eps 1e-7 #define N 105 #define M 1000000007 using namespace std; int m,n,T,t,x,y,u; char a[N],b[N]; int ch[N*2][2],num; int v[N*2]; int d[N][N][N*2][4]; int f[N*2],last[N*2]; int idx(char c) { if(c=='R')return 1; return 0; } void init() { num=1; memset(d,-1,sizeof(d)); memset(ch,0,sizeof(ch)); memset(v,0,sizeof(v)); memset(last,0,sizeof(last)); } void insert(char str[],int val) { int u=0; for(int i=0;str[i];i++) { int c=idx(str[i]); if(ch[u][c]==0) { ch[u][c]=num++; } u=ch[u][c]; } v[u]|=(1<<val); last[u]=v[u]; } void getac() { queue<int>q; f[0]=0; for(int c=0;c<2;c++) { int u=ch[0][c]; if(u) { q.push(u); f[u]=0; // last[u]=0;//WA,意义改变了！ } } while(!q.empty()) { int r=q.front(); q.pop(); for(int i=0;i<2;i++) { int u=ch[r][i]; if(u) { q.push(u); int s=f[r]; f[u]=ch[s][i]; last[u]|=v[f[u]]?v[f[u]]:v[last[f[u]]];//表示到此出现的值 } else ch[r][i]=ch[f[r]][i]; } } } int dp(int x,int y,int u,int s) { if(x==n&&y==m) { return s==3; } int &ans=d[x][y][u][s]; if(ans!=-1)return ans; ans=0; if(x<n) { int v=ch[u][0]; int ss=s|last[v]; ans+=dp(x+1,y,v,ss); ans%=M; } if(y<m) { int v=ch[u][1]; int ss=s|last[v]; ans+=dp(x,y+1,v,ss); ans%=M; } return ans; } int main() { #ifndef ONLINE_JUDGE freopen("ex.in","r",stdin); #endif scanf("%d",&T); while(T--) { scanf("%d%d",&m,&n); scanf("%s",a); scanf("%s",b); init(); insert(a,0); insert(b,1); getac(); printf("%d ",dp(0,0,0,0)); } return 0; }