AC 自动机和 dp

Password Suspects

针对0m100 \leqslant m \leqslant 10,容易想到可以对子串状态压缩
mm 个串,k[0,m1]k \in [0, m-1] 插入 AC 自动机,insert(Sk,k)\text{insert}(S_k, k)
对于表示SkS_k 的末尾节点pp,令val(p)=(1k)\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,n1]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 的边界为ini \geqslant n
    如果sta=(1M)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=staval(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=staval(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) 满足in,sta=(1M)1i \geqslant n, sta = (1 \ll M)-1
是一个合法的结果vecstr\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;
}
}
}