AC 自动机和 dp

Password Suspects

针对 0⩽m⩽100 \leqslant m \leqslant 10，容易想到可以对子串状态压缩
mm 个串，k∈[0,m−1]k \in [0, m-1] 插入 AC 自动机，insert(Sk,k)\text{insert}(S_k, k)
对于表示 SkS_k 的末尾节点 pp，令 val(p)∣=(1≪k)\text{val}(p) \mid = (1 \ll k)
其中 val(p)\text{val}(p) 表示 pp 这个节点是表示哪几个串

在 AC 自动机上执行状态压缩 dp，转移方程如下

f(i,sta,p)→∀c, p2=t(p,c)f(i+1,sta2,p2)f(i, sta, p) \xrightarrow{\forall c, \ p_2 = t(p, c)} f(i+1, sta_2, p_2)

其中 i∈[0,n−1]i \in [0, n-1] 表示 dp 的阶段，stasta 表示用了哪些子串
pp 表示当前 dp 过程在 AC 自动机上的节点，f(i,sta,p)f(i, sta, p) 表示当前状态下，可能的密码个数

针对这一状态表示，可以采用记忆化搜索 f(i,sta,p)f(i, sta, p)

  • 记忆化 dp 的边界为 i⩾ni \geqslant n
    如果 sta=(1≪M)−1, f=1sta = (1 \ll M) -1, \ f = 1，否则的话 f=0f = 0
    （因为所有子串都要被用上）
  • 接下来从 pp 节点开始，对 AC 自动机自底向上搜索

    f(i,sta,p)=∑∀c, p2=t(p,c)f(i+1,sta2,p2)f(i, sta, p) = \sum_{\forall c, \ p_2 = t(p, c)} f(i+1, sta_2, p_2)

    其中 sta2=sta∣val(p2)sta_2 = sta \mid \text{val}(p_2)
  • 所求的答案为 f(0,0,0)f(0, 0, 0)

本例还要求输出具体的方案，同样可以采用记忆化搜索的过程
如果 f(i,sta,p)f(i, sta, p) 合法（f>0f > 0），那么尝试转移
f(i,sta,p)→f(i+1,sta2,p2)f(i, sta, p) \rightarrow f(i+1, sta_2, p_2)
其中 ∀c,p2=t(p,c), sta2=sta∣val(p2)\forall c, p_2 = t(p, c), \quad \ sta_2 = sta \mid \text{val}(p_2)
然后令 str+=c\text{str} += c

如果 print(i,sta,p,str)\text{print}(i, sta, p, str) 满足 i⩾n,sta=(1≪M)−1i \geqslant n, sta = (1 \ll M)-1
是一个合法的结果 vec←str\text{vec} \leftarrow str

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
const int maxn = 100 + 10, SZ = 26, maxs = 1<<10 + 5;
int n, m;
ll f[30][maxs][maxn];
vector<string> vec;

class AC {
public:
    int t[maxn][SZ], fail[maxn], val[maxn];
    int tot = 0;

    void clear() {
        tot = 0;
        memset(t, 0, sizeof t);
        memset(fail, 0, sizeof fail);
        memset(val, 0, sizeof val);
    }

    void insert(const string &str, int idx) {
        int p = 0;
        for (auto x : str) {
            int c = x - 'a';
            if (!t[p][c]) t[p][c] = ++tot;
            p = t[p][c];
        }
        val[p] |= (1<<idx);
    }
    void build() {
        queue<int> que;
        for (int i = 0; i < SZ; i++) {
            if (t[0][i]) que.push(t[0][i]);
        }
        while (que.size()) {
            auto u = que.front(); que.pop();
            for (int i = 0; i < SZ; i++) {
                if (t[u][i]) {
                    fail[t[u][i]] = t[fail[u]][i];
                    que.push(t[u][i]);
                }
                else t[u][i] = t[fail[u]][i];
            }
            val[u] |= val[fail[u]];
        }
    }
} ac;

void init() {
    memset(f, -1, sizeof f);
}

ll dp(int i, int sta, int p) {
    if (i >= n) {
        return sta == (1<<m)-1 ? 1 : 0;
    }
    if (f[i][sta][p] != -1) return f[i][sta][p];

    ll &res = f[i][sta][p];
    res = 0;
    for (int c = 0; c < SZ; c++) {
        int p2 = ac.t[p][c];
        res += dp(i+1, sta | ac.val[p2], p2);
    }
    return res;
}

void out(int i, int sta, int p, string str) {
    if (i >= n) {
        if (sta == (1<<m)-1) vec.push_back(str);
        return;
    }
    if (f[i][sta][p] <= 0) return;

    for (int c = 0; c < SZ; c++) {
        int p2 = ac.t[p][c];
        int sta2 = sta | ac.val[p2];
        char s = 'a'+c;
        out(i+1, sta2, p2, str+s);
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int cas = 0;
    while (scanf("%d%d", &n, &m) == 2 && n) {
        printf("Case %d: ", ++cas);
        ac.clear();
        init();

        // get data
        for (int i = 0; i < m; i++) {
            string str;
            cin >> str;
            ac.insert(str, i);
        }

        // build
        ac.build();

        // dp
        ll ans = dp(0, 0, 0);
        printf("%lld", ans);

        printf(" suspects\n");

        // then output solution
        if (ans <= 42) {
            vec.clear();
            out(0, 0, 0, "");
            sort(vec.begin(), vec.end());
            for (auto s : vec) cout << s << endl;
        }
    }
}