[AC自动机][状态压缩DP][DFS]

题目链接： Password Suspects

这题让我回想起了某现场赛被某大佬支配的恐惧

感觉是dp，而且这个子串的数据量一看就是状压，然后在推转移方程的时候死活推不出来一个不交叉的。可耻的搜了题解，看到大佬们的标题：AC自动机+DP
我就

~~其实是常见的一种操作只是我太久没做过字符串的题目了~~
在思考递推方程的时候就一直在纠结前缀与后缀重合的这种情况怎么表示状态，然后忽然意识到ac自动机（更确切的说是Trie图）就是可以唯一的确定一个匹配状态的数据结构！这种题一般都是给定一些字串，然后给出一些约束条件，比如要求

• 匹配所有字串，这种就是本题类型的，往往需要状压
• 不能匹配任一字串，即匹配走过的路径上不能有任何一个危险节点
• 满足某些条件的字串
• 等等等等（我还没来得及总结那么多

个人理解的话，AC自动机在这种dp里的作用往往是保证状态的无后效性和递推构造的合法性，可以说Trie图是给了一个递推的方向

然后说本题的话，可以构造一个状态\[dp(l,S,u)\]表示:

从根节点开始走了l步走到了ac自动机上的u节点且此时已经包括的子串集合为S的情况下还能构造多少个合法的字符串

这样的话显然答案是dp(0,0,0),然后有了Trie图的指引可以得到递推方程为\[ dp(l,S,u)=\sum dp(l+1,S|val[v],v)\] ,其中v是u在Trie图中的孩子节点，val[u]表示以u节点为结尾的所有的子串集合，当然也是一个二进制状压集合，由于要包括所有的后缀，这个东西在建立ac自动机的时候需要每次都val[u]|=fail[val[u]]，明白ac自动机建立过程的话这个应该不难理解。

边界条件是，当走了n步到达某个u节点之后，如果这时已经集齐了所有的子串那么就返回1，否则就返回0（没有集齐那不就不合法吗肯定是0个233），写成公式是

\[
dp(n,S,u)=
\begin{cases}
1& \ S=2^{m}-1\\
0& \ S\neq 2^{m}-1
\end{cases}
\]

附上跑的超慢的代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

const double pi = acos(-1.0);
const int mod=1e9+7;
const int maxn=2e3+1;
const int maxnode=500+5;

char tmp[100];

struct Trie{
    int ch[maxnode][26],val[maxnode],fail[maxnode];
    LL dp[30][1050][maxnode];
    bool vis[30][1050][maxnode];
    char ans[30];
    int sz,root,n,m;
    int newnode(){
        int u=++sz;
        memset(ch[u],-1,sizeof(ch[0]));
        return u;
    }
    void init(){
        sz=root=0;
        memset(ch[root],-1,sizeof(ch[0]));
        memset(fail,0,sizeof(fail));
        memset(dp,-1,sizeof(dp));
        memset(vis,0,sizeof(vis));
        memset(val,0,sizeof(val));
    }
    
    int idx(char c){return (int)c-'a';}
    void insert(char *s,int x){
        int len=strlen(s),u=root;
        for(int i=0;i<len;u=ch[u][idx(s[i])],++i){
            if(ch[u][idx(s[i])]==-1){//error2
                ch[u][idx(s[i])]=newnode();
            }
        }
        val[u]|=(1<<(x-1));
    }
    void build(){
        queue<int> Q;
        for(int i=0;i<26;i++){
            if(ch[0][i]==-1)
                ch[0][i]=0;
            else{
                fail[ch[0][i]]=0;
                Q.push(ch[0][i]);
            }
        }
        while(!Q.empty()){
            int c=Q.front();Q.pop(),val|=val[fail];
            for(int i=0;i<26;i++){
                if(ch[i]==-1)
                    ch[i]=ch[fail][i];
                else{
                    fail[ch[i]]=ch[fail][i];
                    Q.push(ch[i]);
                }
            }
        }
    }
    LL dps(int l,int S,int u){
        if(~dp[l][S][u]) return dp[l][S][u];
        if(l==n) return dp[l][S][u]=((S==(1<<m)-1)?1:0);
        LL res=0;
        for(int i=0;i<26;i++)
            res+=dps(l+1,S|val[ch[u][i]],ch[u][i]);//error1
        return dp[l][S][u]=res;
    }
    void dfs(int l,int S,int u){
        //cout<<ans<<endl;
        //if(vis[l][S][u]) return ;
        //vis[l][S][u]=1;//error3
        if(l==n&&(S==(1<<m)-1)){
            ans[l]='\0';
            printf("%s\n",ans);
            return ;
        }
        for(int i=0;i<26;i++){
            ans[l]=i+'a';
            if(dp[l+1][S|val[ch[u][i]]][ ch[u][i]] )dfs(l+1,S|val[ch[u][i]],ch[u][i]);
        }
    }
}tr;

int main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0),cout.tie(0);
    int n,m,cs=0;
    LL ans;
    while(~scanf("%d%d",&n,&m)&&n){
        cs++;tr.init(),tr.n=n,tr.m=m;
        for(int i=1;i<=m;i++){
            scanf(" %s",tmp);
            tr.insert(tmp,i);
        }
        tr.build();
        ans=tr.dps(0,0,0);
        printf("Case %d: %lld suspects\n",cs,ans);
        if(ans<=42)
            tr.dfs(0,0,0);
    }
    return 0;
}
/*
10 2
hello
world
10 0
4 1
icpc
0 0

*/