ac自动机匹配模式串题目(非板子)

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
 
const int MOD = 20090717;
 
int n, m, k;
int trie[100][26];//trie树
int state[100];//节点匹配状态
int fail[100];//失败指针
int cnt;//trie树节点计数
 
int dp[2][100][1024];//滚动（步数的奇偶）、到哪个节点、匹配到什么模式串
 
int popcount(int x) {
    int res = 0;
    while (x) {
        res += x & 1;
        x >>= 1;
    }
    return res;
}
 
void init_ac() {
    cnt = 1;
    memset(trie[0], 0, sizeof(trie[0]));
    state[0] = 0;
}
 
void insert(string s, int idx) {
    int p = 0;
    for (char c : s) {
        int i = c - 'a';
        if (!trie[p][i]) {
            memset(trie[cnt], 0, sizeof(trie[cnt]));
            state[cnt] = 0;
            trie[p][i] = cnt++;
        }
        p = trie[p][i];
    }
    state[p] |= (1 << idx);//标记匹配到idx下标的串
}
 
void build_ac() {
    queue<int> q;
    vector<int> order;
    fail[0] = 0;
    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 u = q.front();
        q.pop();
        order.push_back(u);
        for (int i = 0; i < 26; i++) {
            if (trie[u][i]) {//如果存在儿子，爹帮儿子建回跳边，儿子入队
                int v = trie[u][i];
                fail[v] = trie[fail[u]][i];
                q.push(v);
            }
            else {
                trie[u][i] = trie[fail[u]][i];//否则，爹自建转移边
            }
        }
    }
    for (int u : order) {
        state[u] |= state[fail[u]];//将每个节点的状态与其失败指针指向的节点的状态进行合并
    }
}
 
int main() {
    while (cin >> n >> m >> k) {
        if (n == 0 && m == 0 && k == 0) break;
        init_ac();
        for (int i = 0; i < m; i++) {
            string s;cin >> s;
            insert(s, i);
        }
        build_ac();
 
        memset(dp[0], 0, sizeof(dp[0]));
        dp[0][0][0] = 1;
        int cur = 0;
        for (int i = 0; i < n; i++) {
            int nxt = cur ^ 1;
            memset(dp[nxt], 0, sizeof(dp[nxt]));
            for (int j = 0; j < cnt; j++) {
                for (int mask = 0; mask < (1 << m); mask++) {
                    if (dp[cur][j][mask] == 0) continue;
                    for (char c = 'a'; c <= 'z'; c++) {//随机选一个方向，在自动机上走
                        int nxt_node = trie[j][c - 'a'];
                        int nxt_mask = mask | state[nxt_node];
                        dp[nxt][nxt_node][nxt_mask] = (dp[nxt][nxt_node][nxt_mask] + dp[cur][j][mask]) % MOD;
                    }
                }
            }
            cur = nxt;
        }
        int ans = 0;
        for (int j = 0; j < cnt; j++) {
            for (int mask = 0; mask < (1 << m); mask++) {
                if (popcount(mask) >= k) {
                    ans = (ans + dp[cur][j][mask]) % MOD;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}