nefu 2027Ac自动机 + 状压dp

想不出来啊 想不出来😟（全局变量数组开大还会RE。。。。。）
官方题解:**多模式串匹配的问题用 AC 自动机来解决。**首先用输入的这些串构建出 AC 自动机，然后用状压在 AC 自动机上对答案进行搜索。设 res[now][S][l]，表示的意思是在自动机上当前节点为 now，状态是 S，已经匹配的长度为 l，有多少种方案数。用记忆化搜索将答案统计出来，就可以了。
问题
1） 为什么可以用状压dp解决呢
当此问题没有任何限制时，本题求的即为26的n次幂。对应代码

LL dfs(int l)
{
    if(l==n){return 1;}
    if(dp[l]) return dp[l];
    LL ans=0;
    for(int i=1;i<=26;i++){
        ans=(ans+dfs(l+1))%mod;;
    }
    return dp[l]=ans;;
}

显然其中多算了一些不包含题目所给子串的答案，那么我们如何约束呢？
利用二进制存储信息的思想，把第i个串对应的Trie节点标记为 1<<(i-1)
所以只要我们在dfs答案时记录一个状态sta，当sta==1<<m-1时才计算答案即return1否则return 0 。这就可以完美的得到答案。
2）怎样记录当前的状态
当我们在Trie上建立过fail指针，并进行路径压缩后，那么一直枚举字母可以就看做一直在Trie上进行节点匹配。同时在build Trie 时把每个模式串结尾打上1）问的标记，然后我们再利用fail指针更新Trie上的每个节点所对应的状态

 while(!q.empty()){
            int p=q.front();q.pop();

            is[p]=is[p]|is[fail[p]];//画重点

3） 状压dp的时间复杂度合理性

利用fail指针把每个可以成为模式串结尾的节点标记成对应的状态
具体看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=105;
const LL mod=1e9+7;
int fail[maxn+6],is[maxn+6],tot,trie[maxn][26],n,m;
LL dp[105][(1<<10)+10][30];
char s[maxn+6];  
queue<int>q;
struct Ac_auto
{
    void add(char *s,int id){
        int len=strlen(s),p=0;
        for(int i=0;i<len;i++){
            int c=s[i]-'a';
            if(!trie[p][c]){
                trie[p][c]=++tot;
            }
            p=trie[p][c];
        }
        is[p]|=1<<id;
    }
    void build_fail(){
        while(!q.empty()) q.pop();
        for(int i=0;i<26;i++){
            if(trie[0][i]) fail[trie[0][i]]=0,q.push(trie[0][i]);
        }

        while(!q.empty()){
            int p=q.front();q.pop();

            is[p]=is[p]|is[fail[p]];

            for(int i=0;i<26;i++){
                if(trie[p][i]){
                    fail[trie[p][i]]=trie[fail[p]][i];
                    q.push(trie[p][i]);
                }
                else
                    trie[p][i]=trie[fail[p]][i];
            }
        }
    }
}ac;
LL dfs(int now,int state,int l)
{
    if(l==n){
        if(state==(1<<m)-1) return 1;
        return 0;
    }

    if(dp[now][state][l]!=-1) return dp[now][state][l];
    int ans=0,p;
    for(int i=0;i<26;i++){
        p=trie[now][i];
        ans=(ans+dfs(p,is[p]|state,l+1))%mod;
    }
    dp[now][state][l]=ans;
    return ans;
}
int main()
{
   memset(dp,-1,sizeof dp);
   scanf("%d %d",&n,&m);
   for(int i=1;i<=m;i++){
       scanf("%s",s);
       ac.add(s,i-1);
   }
   ac.build_fail();
   printf("%lld\n",dfs(0,0,0));
}