HDU 2825 Wireless Password-AC自動機+DP

給m個單詞，由這m個單詞組成的一個新單詞（兩個單詞可以重疊包含）長度為n，且新單詞中包含的基本單詞數目不少於k個。問這樣的新單詞共有多少個？

m很小，用二進制表示新單詞中包含基本單詞的情況。

用m個單詞建立AC自動機，可以求出所有單詞之間相互包含的情況，AC自動機的後綴特性（每個結點的失配邊指向新結點，新節點到trie樹根的字符串是當前節點字符串的後綴）。

動態規劃：

f(i, j, k)：長度為i的單詞，在trie樹中第j個結點處，包含基本單詞的情況為k（二進制），的總方案數。

轉移方程：

在當前字符串後邊再加上一個字母

f(i+1, u, k|val[u]) += f(i, j, k)

u是j結點的子結點（或者是失配邊指向的結點），k|val[u]表示加上一個新字母後包含基本單詞的情況。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
struct AC_Automata {
    #define N 102
    #define M 26
    int ch[N][M], val[N], last[N], f[N], sz;
    void clear() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); }
    int idx(char c) { return c-'a'; }

    void insert(char s[], int v) {
        int u = 0;
        for (int i=0; s[i]; i++) {
            int c = idx(s[i]);
            if (!ch[u][c]) {
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz] = 0;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        val[u] = 1<<v;
    }
    void build() {
        queue<int> q;
        f[0] = 0;
        for (int c=0; c<M; c++) {
            int u = ch[0][c];
            if (u) { f[u] = last[u] = 0; q.push(u); }
        }
        while (!q.empty()) {
            int r = q.front(); q.pop();
            for (int c=0; c<M; c++) {
                int u = ch[r][c];
                if (!u) {
                    ch[r][c] = ch[f[r]][c];
                    val[r] = val[r] | val[f[r]];  //從根到當前結點組成的字符串後綴包含基本單詞的情況（傳遞）
                    continue;
                }
                q.push(u);
                f[u] = ch[f[r]][c];
                last[u] = val[f[u]] ? f[u] : last[f[u]];
            }
        }
    }
} ac;
int c[1030]; ///記錄每個狀態含有幾個串
int f[27][102][1025];

void init() {
    memset(c, 0, sizeof(c));
    for (int i=0; i<1024; i++) {
        for (int j=0; j<10; j++)
            if ((1<<j) & i) c[i]++;
    }
}
void solve(int n, int m, int p) {
    #define Mod 20090717
    int u;
    for (int i=0; i<=n; i++)
        for (int j=0; j<ac.sz; j++)
            for (int k=0; k<(1<<m); k++)
                f[i][j][k] = 0;
    f[0][0][0] = 1;

    for (int i=0; i<n; i++)
        for (int j=0; j<ac.sz; j++) {
            for (int k=0; k<(1<<m); k++) {
                if (f[i][j][k] == 0) continue;
                for (int jj=0; jj<M; jj++) {
                    u = ac.ch[j][jj];
                    f[i+1][u][ac.val[u]|k] = (f[i+1][u][ac.val[u]|k] + f[i][j][k]) % Mod;
                }
            }
        }

    int ans = 0;
    for (int i=0; i<ac.sz; i++)
        for (int j=0; j<(1<<m); j++)
            if (c[j] >= p) ans = (ans + f[n][i][j]) % Mod;
    printf("%d\n", ans);
}
int main() {
    int n, m, k;
    char s[12];
    init();

    while (scanf("%d%d%d", &n, &m, &k) == 3) {
        if (n == 0 && m == 0 && k == 0) break;
        ac.clear();

        for (int i=0; i<m; i++) {
            scanf(" %s", s);
            ac.insert(s, i);
        }
        ac.build();

        solve(n, m, k);

    }
    return 0;
}