题意 : 给出一个 n 行、m 列的方格图，现从图左上角(0, 0) 到右下角的 (n, m)走出一个字符串(规定只能往下或者往右走)，向右走代表' R ' 向下走则是代表 ' D ' 最后从左上角到右下角，不同的路线会走出不同的字符串，问你这些不同的字符串有多少个是包含了接下来给定的两个子串。
分析 : 简单想想不难发现最后肯定是走了 (n+1) 个 ' D ' 和 (m+1)个 ' R ' ，那么也就是说用 (n+1) 个 ' D ' 和 (m+1)个 ' R ' 构造出长度为 (n+m+2) 的字符串，且包含给定的两个子串的方案数有多少个（ 跟 HDU 3341 类似 ），那么来看看关键点，即考虑 ' D '与' R '的数量、以及当前节点包含了多少个子串、当前停留在Trie上哪个节点，那么可以定义出DP[i][j][k][l]代表在有 i 个 ' D '（即向下走了 i 步）、j 个 ' R '（向右走 j 步）、停留在 k 这个节点、包含子串情况 l 时的最大方案数，则状态转移方程为
每个节点能向 ' D ' 和 ' R ' 转移，这里以向 ' D ' 转移为例
DP[i+1][j][k][l | Trie[k]['D'].id] += DP[i][j][k][l] ( Trie[k]['D']代表从 k 转移到状态为' D '节点，其 id 表示包含字母的情况 )
DP初始状态为 DP[0][0][0][0] = 1、DP其他 = 0
#include<bits/stdc++.h> using namespace std; const int Max_Tot = 210; const int Letter = 2; const int MOD = 1000000007; int n, m; int dp[110][110][210][4]; struct Aho{ struct StateTable{ int Next[Letter]; int fail, id; }Node[Max_Tot]; int Size; queue<int> que; inline void init(){ while(!que.empty()) que.pop(); memset(Node[0].Next, 0, sizeof(Node[0].Next)); Node[0].fail = Node[0].id = 0; Size = 1; } inline void insert(char *s, int id){ int now = 0; for(int i=0; s[i]; i++){ int idx = (s[i] == 'D'); if(!Node[now].Next[idx]){ memset(Node[Size].Next, 0, sizeof(Node[Size].Next)); Node[Size].fail = Node[Size].id = 0; Node[now].Next[idx] = Size++; } now = Node[now].Next[idx]; } Node[now].id |= (1<<id); } inline void BuildFail(){ Node[0].fail = 0; for(int i=0; i<Letter; i++){ if(Node[0].Next[i]){ Node[Node[0].Next[i]].fail = 0; que.push(Node[0].Next[i]); }else Node[0].Next[i] = 0; } while(!que.empty()){ int top = que.front(); que.pop(); Node[top].id |= Node[Node[top].fail].id; for(int i=0; i<Letter; i++){ int &v = Node[top].Next[i]; if(v){ que.push(v); Node[v].fail = Node[Node[top].fail].Next[i]; }else v = Node[Node[top].fail].Next[i]; } } } }ac; int Solve() { for(int i=0; i<=n; i++) for(int j=0; j<=m; j++) for(int k=0; k<ac.Size; k++) for(int l=0; l<4; l++) dp[i][j][k][l] = 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<ac.Size; k++){ for(int l=0; l<4; l++){ if(dp[i][j][k][l] > 0){ int Node1 = ac.Node[k].Next[0]; int Node2 = ac.Node[k].Next[1]; dp[i][j+1][Node1][l | ac.Node[Node1].id] += dp[i][j][k][l]; dp[i+1][j][Node2][l | ac.Node[Node2].id] += dp[i][j][k][l]; dp[i][j+1][Node1][l | ac.Node[Node1].id] %= MOD; dp[i+1][j][Node2][l | ac.Node[Node2].id] %= MOD; } } } } } int ans = 0; for(int i=0; i<ac.Size; i++){ ans += dp[n][m][i][3]; ans %= MOD; } return ans%MOD; } char S[111]; int main(void) { int nCase; scanf("%d", &nCase); while(nCase--){ scanf("%d %d", &m, &n); ac.init(); for(int i=0; i<2; i++){ scanf("%s", S); ac.insert(S, i); }ac.BuildFail(); printf("%d ", Solve()); } return 0; }