2 3 2 RRD DDR 3 2 R D
1 10
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pair<int,int>pil;
const int INF = 0x3f3f3f3f;
const int MOD=1e9+7;
int dp[110][110][210][4];
int n,m;
struct AC{
int next[220][2];
int fail[220],ed[220];
int root,L;
int newnode()
{
for(int i=0;i<2;i++)
next[L][i]=-1;
ed[L++]=0;
return L-1;
}
void init()
{
L=0;
root=newnode();
}
int what(char c)
{
return c!='D';
}
void Insert(char buf[],int id)
{
int len=strlen(buf);
int now=root;
for(int i=0;i<len;i++)
{
int x=what(buf[i]);
if(next[now][x]==-1)
next[now][x]=newnode();
now=next[now][x];
}
ed[now]|=(1<<id);
}
void Build_AC()
{
queue<int>q;
fail[root]=root;
for(int i=0;i<2;i++)
{
if(next[root][i]==-1)
next[root][i]=root;
else
{
fail[next[root][i]]=root;
q.push(next[root][i]);
}
}
while(!q.empty())
{
int now=q.front();
q.pop();ed[now]|=ed[fail[now]];
for(int i=0;i<2;i++)
{
if(next[now][i]==-1)
next[now][i]=next[fail[now]][i];
else
{
fail[next[now][i]]=next[fail[now]][i];
q.push(next[now][i]);
}
}
}
}
void solve()//0:D 1:R
{
CLEAR(dp,0);
dp[0][0][0][0]=1;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
for(int k=0;k<L;k++)
{
for(int l=0;l<(1<<2);l++)
{
if(dp[i][j][k][l])
{
if(i<n)
{
int x=next[k][0];
int st=l|ed[x];
dp[i+1][j][x][st]+=dp[i][j][k][l];
dp[i+1][j][x][st]%=MOD;
}
if(j<m)
{
int x=next[k][1];
int st=l|ed[x];
dp[i][j+1][x][st]+=dp[i][j][k][l];
dp[i][j+1][x][st]%=MOD;
}
}
}
}
}
}
int ans=0;
for(int i=0;i<L;i++)
{
ans+=dp[n][m][i][3];
ans%=MOD;
}
printf("%d\n",ans);
}
};
AC A;char str[110];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
A.init();
scanf("%d%d",&m,&n);
REP(i,2)
{
scanf("%s",str);
A.Insert(str,i);
}
A.Build_AC();
A.solve();
}
return 0;
}
/*
2
3 2
RRD
DDR
3 2
R
D
*/
HDU 4758 Walk Through Squares(自动机+DP)
原文：http://blog.csdn.net/u013582254/article/details/45179917