HDU 4758——Walk Through Squares——2013 ACM/ICPC Asia Regional Nanjing Online

与其说这是一次重温AC自动机+dp，倒不如说这是个坑，而且把队友给深坑了。

这个题目都没A得出来，我只觉得我以前的AC自动机的题目都白刷了——深坑啊。

题目的意思是给你两个串，每个串只含有R或者D，要求有多少种长为（n+m）的串（其中有n个R，m个D）同时含有这两个串作为子串。（我就不说题目描述了）

看完了题目我居然一开始用排列组合去做，搞了近一个小时，深坑队友啊。

其实正解是用AC自动机来dp出解的。

什么意思呢？把两个给定的串放到AC字典树上，并且弄好fail指针，变为tire图，构造好AC自动机，然后就是dp了！

怎么dp呢？

可以这样来做，f[x][y][z][k]表示在第x个点，走了y个R，z个D，含有串的情况为k的种类数。

xyz就不用解释了，一看就懂，k是怎么表示状态数的呢？1表示有1个串，2表示两个串？显然不行，到时候有重复的你怎么判断啊 ？

这里k其实是用二进制来表示的，由于每次只有两个串，所有我们用00表示都不含，01表示含有第一个串，10表示含有第二个串，11表示两串都含有。

这样k就只要4就可以了。；

接下来就是自动机和dp的知识了。

我的这个代码写得很冗，效率灰常地低，希望大家不要见怪，我也是为了保险起见。

一开始我还M了好多发，注意这个题目一般至少要32M的内存才能过，hdu上那些900多k的代码我不知道是怎么来的。所以对我来说这个题目还有一点点卡内存的赶脚。

诶不说了说多了都是泪，上代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#define maxn 201

#define maxm 101

#define M 1000000007

using namespace std;

int next[maxn][2],f[maxn][maxm][maxm][4],fail[maxn],N,tag[maxn],t,n,m;

char s0[maxn];

void clear()

{

    N=0;

    memset(next,0,sizeof next);

    memset(f,0,sizeof f);

    memset(fail,0,sizeof fail);

    memset(tag,0,sizeof tag);

}

void insert(char s[],int code)

{

    int tep,now=0;

    for (int i=0; s[i]; i++)

    {

        if (s[i]=='R') tep=0; else tep=1;

        if (!next[now][tep]) next[now][tep]=++N;

        now=next[now][tep];

    }

    tag[now]=(1<<(code-1));

}

void buildAC()

{

    queue<int>Q;

    int now,k,child;

    Q.push(0);

    while (!Q.empty())

    {

        now=Q.front(),Q.pop();

        for (int i=0; i<2; i++)

        {

            child=next[now][i];

            if (child)

            {

                Q.push(child);

                if (now==0) fail[child]=0;

                else

                {

                    k=fail[now];

                    while (k && !next[k][i]) k=fail[k];

                    if (next[k][i]) fail[child]=next[k][i];

                        else fail[child]=0;

                }

                tag[child]|=tag[fail[child]];

            }

            else

            {

                k=fail[now];

                next[now][i]=next[k][i];

            }

        }

    }

}

int main()

{

    int cur,num,ans;

    scanf("%d",&t);

    while (t--)

    {

        clear();

        scanf("%d%d",&n,&m);

        scanf("%s",s0);  insert(s0,1);

        scanf("%s",s0);  insert(s0,2);

        buildAC();

        f[0][0][0][0]=1;//第0个点，走0步R，走0步D，取得的状态为00

        for (int i=0; i<n+m; i++)//总步数

        {

                for (int k1=0; k1<=min(n,i); k1++)//k1步R

                {

                    int k2=i-k1;

                    for (int p=0; p<=N; p++)

                    {

                        for (int k=0; k<=3; k++)

                        {

                            if (f[p][k1][k2][k])

                            {

                                if (k1<n)

                                {

                                    cur=next[p][0];

                                    num=tag[cur]|k;

                                    f[cur][k1+1][k2][num]+=f[p][k1][k2][k];

                                    f[cur][k1+1][k2][num]%=M;

                                }

                                if (k2<m)

                                {

                                    cur=next[p][1];

                                    num=tag[cur]|k;

                                    f[cur][k1][k2+1][num]+=f[p][k1][k2][k];

                                    f[cur][k1][k2+1][num]%=M;

                                }

                            }

                        }

                    }

                }

        }

        ans=0;

        for (int i=0; i<=N; i++) ans=(ans+f[i][n][m][3])%M;

        printf("%d\n",ans);

    }

    return 0;

}