HDU 4758 Walk Through Squares(AC自动机+DP)

难得出一个AC自动机，我还没做到这个题呢。。。这题思路不难想，小小的状压出一维来，不过，D和R，让我wa死了，AC自动机，还得刷啊。。。
  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<cmath>
  5 #include<algorithm>
  6 using namespace std;
  7 #define MOD 1000000007
  8 int dp[101][101][201][4];
  9 int trie[201][2];
 10 int o[201];
 11 int fail[201],que[1001],p[201][201];
 12 int t;
 13 void CL()
 14 {
 15     t = 1;
 16     memset(trie,-1,sizeof(trie));
 17     memset(o,0,sizeof(o));
 18     memset(p,0,sizeof(p));
 19 }
 20 void insert(char *s,int x)
 21 {
 22     int i,root,len,temp;
 23     len = strlen(s);
 24     root = 0;
 25     for(i = 0; i < len; i ++)
 26     {
 27         temp = s[i] == 'D' ? 1:0;
 28         if(trie[root][temp] == -1)
 29             trie[root][temp] = t ++;
 30         root = trie[root][temp];
 31     }
 32     o[root] = 1<<x;
 33 }
 34 void build_ac()
 35 {
 36     int head,tail,front,i;
 37     head = tail = 0;
 38     for(i = 0; i < 2; i ++)
 39     {
 40         if(trie[0][i] != -1)
 41         {
 42             fail[trie[0][i]] = 0;
 43             que[tail++] = trie[0][i];
 44         }
 45         else
 46             trie[0][i] = 0;
 47     }
 48     while(head != tail)
 49     {
 50         front = que[head++];
 51         o[front] |= o[fail[front]];
 52         for(i = 0; i < 2; i ++)
 53         {
 54             if(trie[front][i] != -1)
 55             {
 56                 que[tail++] = trie[front][i];
 57                 fail[trie[front][i]] = trie[fail[front]][i];
 58             }
 59             else
 60             {
 61                 trie[front][i] = trie[fail[front]][i];
 62             }
 63         }
 64     }
 65 }
 66 int main()
 67 {
 68     int cas,i,j,k,u,n,m,temp;
 69     char str[101];
 70     scanf("%d",&cas);
 71     while(cas--)
 72     {
 73         CL();
 74         scanf("%d%d",&n,&m);
 75         for(i = 0; i < 2; i ++)
 76         {
 77             scanf("%s",str);
 78             insert(str,i);
 79         }
 80         for(i = 0; i <= n; i ++)
 81         {
 82             for(j = 0; j <= m; j ++)
 83             {
 84                 for(k = 0; k < t; k ++)
 85                 {
 86                     for(u = 0; u < 4; u ++)
 87                         dp[i][j][k][u] = 0;
 88                 }
 89             }
 90         }
 91         build_ac();
 92         dp[0][0][0][0] = 1;
 93         for(i = 0; i <= n; i ++)
 94         {
 95             for(j = 0; j <= m; j ++)
 96             {
 97                 for(k = 0; k < t; k ++)
 98                 {
 99                     for(u = 0; u < 4; u ++)
100                     {
101                         if(i != n)
102                         {
103                             temp = trie[k][0];
104                             dp[i+1][j][temp][u|o[temp]] = (dp[i+1][j][temp][u|o[temp]] + dp[i][j][k][u])%MOD;
105                         }
106                         if(j != m)
107                         {
108                             temp = trie[k][1];
109                             dp[i][j+1][temp][u|o[temp]] = (dp[i][j+1][temp][u|o[temp]] + dp[i][j][k][u])%MOD;
110                         }
111                     }
112                 }
113             }
114         }
115         int ans = 0;
116         for(i = 0; i < t; i ++)
117         {
118             ans = (ans + dp[n][m][i][3])%MOD;
119         }
120         printf("%d
",ans);
121     }
122     return 0;
123 }