AC自动机+DP luoguP4052 and P3311

https://www.luogu.com.cn/problem/P4052
题意： 求长度为m的小写字母组成的字符串ss中包含给定字符串集合S中任意一个为子串的ss个数。
思路： 经典的在ac自动机上跑dp的套路，长度为m的不包含S中任意子串的字符串ss的个数等价于trie图上长度为m不经过有ed标记的节点以及有fail树上的父亲不含ed标记的节点(后者避免了串s不是字典串但s的后缀是字典串这种情况)

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false) ,cin.tie(0), cout.tie(0);
//#pragma GCC optimize(3,"Ofast","inline")
#define ll long long
#define PII pair<int, int>
//#define int long long
const int N = 1e4 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e4+7;
const double PI = acos(-1.0);

namespace AC {
    int tr[N][26], tot;
    bool e[N]; int fail[N];
    void insert(char *s) {
        int u = 0; 
        for ( int i = 1; s[i]; ++ i ) {
            int ch = s[i] - 'A';
            if(!tr[u][ch]) tr[u][ch] = ++ tot;
            u = tr[u][ch];
        }
        e[u] = 1;
    }
    queue<int> q;
    void build() {
        for ( int i = 0; i < 26; ++ i ) {
            if(tr[0][i]) q.push(tr[0][i]);
        }
        while(q.size()) {
            int u = q.front();
            q.pop();
            for ( int i = 0; i < 26; ++ i ) {
                if(tr[u][i]) {
                    fail[tr[u][i]] = tr[fail[u]][i];
                    e[tr[u][i]] |= e[tr[fail[u]][i]];
                    //避免了串s不是字典串但s的后缀是字典串这种情况
                    q.push(tr[u][i]);
                } else {
                    tr[u][i] = tr[fail[u]][i];
                }
            }
        }
    }
}
char ss[105];
ll f[105][N];
int main() {
    IOS
    int n, m; cin >> n >> m;
    for ( int i = 1; i <= n; ++ i ) {
        cin >> (ss + 1);
        AC::insert(ss);   
    }
    AC::build();
    f[0][0] = 1;
    for ( int i = 1; i <= m; ++ i ) {
        for ( int j = 0; j <= AC::tot; ++ j) {
            for ( int k = 0; k < 26; ++ k ) {
                if(!AC::e[AC::tr[j][k]]) {
                    (f[i][AC::tr[j][k]] += f[i - 1][j]) %= mod;
                }
            }
        }
    }
    ll ans = 0;
    for ( int i = 0; i <= AC::tot; ++ i) {
        (ans += f[m][i]) %= mod;
    }
    ll res = 1;
    for (int i = 1; i <= m; ++ i) res = res * 26 % mod;
    cout << (res - ans + mod) % mod << '\n';
    return 0;
}

https://www.luogu.com.cn/problem/P3311
AC自动机与数位dp结合
注意字典串含前导零，统计的串不能含前导0
那么 有前导0在自动机上就是从0点(字典树的根)开始匹配

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false) ,cin.tie(0), cout.tie(0);
//#pragma GCC optimize(3,"Ofast","inline")
#define ll long long
#define PII pair<int, int>
//#define int long long
const int N = 1e4 + 5;
const int M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);

namespace AC {
    int tr[N][10], tot;
    bool e[N]; int fail[N];
    void insert(char *s) {
        int u = 0; 
        for ( int i = 1; s[i]; ++ i ) {
            int ch = s[i] - '0';
            if(!tr[u][ch]) tr[u][ch] = ++ tot;
            u = tr[u][ch];
        }
        e[u] = 1;
    }
    queue<int> q;
    void build() {
        for ( int i = 0; i < 10; ++ i ) {
            if(tr[0][i]) q.push(tr[0][i]);
        }
        while(q.size()) {
            int u = q.front();
            q.pop();
            for ( int i = 0; i < 10; ++ i ) {
                if(tr[u][i]) {
                    fail[tr[u][i]] = tr[fail[u]][i];
                    e[tr[u][i]] |= e[tr[fail[u]][i]];//
                    q.push(tr[u][i]);
                } else {
                    tr[u][i] = tr[fail[u]][i];
                }
            }
        }
    }
}
ll f[1505][1505]; int num[1505];
int dfs(int pos, int tr_pos, bool limit, bool lead) {
    if(!pos) return !lead;
    if(!limit && !lead && f[pos][tr_pos] != - 1) return f[pos][tr_pos];
    int len = limit ?  num[pos] : 9;
    int res = 0;
    for ( int i = 0; i <= len; ++ i ) {
        if(lead) {
            if(!AC::e[AC::tr[0][i]]) {
                res += dfs(pos - 1, AC::tr[0][i], limit && i == len, lead && !i);
                res %= mod;
            }
        } else {
            if(!AC::e[AC::tr[tr_pos][i]]) {
                res += dfs(pos - 1, AC::tr[tr_pos][i], limit && i == len, lead && !i);
                res %= mod;
            }
        }
    }
    if(!limit && !lead) f[pos][tr_pos] = res;
    return res;
}
char ss[1505];
int cal(string ss) {

    int n = ss.length();
    reverse(ss.begin(), ss.end());
    ss = " " + ss; 
    for ( int i = 1; i <= n; ++ i ) {
        num[i] = ss[i] - '0';
    }
    return dfs(n, 0, 1, 1);
}
int main() {
    IOS
    string n;
    int m; cin >> n >> m;
    for ( int i = 1; i <= m; ++ i ) {
       cin >> (ss + 1); AC::insert(ss); 
    }
    AC::build();
    memset(f, -1, sizeof f);
    cout << cal(n) << '\n';
    return 0;
}