POJ 1. 蓝桥杯 - $Password Suspects$. $AC$ 自动机+状压 $dp$
原题链接
简单
作者:
炽热的
,
2023-03-13 16:14:32
,
所有人可见
,
阅读 101
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long i64;
const int N = 30, M = 410, S = 1 << 11;
int n, m;
char str[N];
int tr[M][26], idx;
int dar[M], ne[M], q[M];
i64 f[N][M][S];
void insert(int id) {
cin >> str;
int p = 0;
for (int i = 0; str[i]; i ++ ) {
int v = str[i] - 'a';
if (!tr[p][v]) tr[p][v] = ++ idx;
p = tr[p][v];
}
dar[p] |= 1 << id;
}
void build() {
int hh = 0, tt = -1;
for (int i = 0; i < 26; i ++ )
if (tr[0][i])
q[ ++ tt] = tr[0][i];
while (hh <= tt) {
int t = q[hh ++ ];
for (int i = 0; i < 26; i ++ ) {
int &p = tr[t][i];
if (!p) p = tr[ne[t]][i];
else {
ne[p] = tr[ne[t]][i];
dar[p] |= dar[ne[p]];
q[ ++ tt] = p;
}
}
}
}
void dfs(int len, int j, int s) {
if (len == n) {
if (s == (1 << m) - 1)
cout << str << endl;
return ;
}
for (int i = 0; i < 26; i ++ ) {
int p = tr[j][i];
if (f[len + 1][p][s | dar[p]] && f[len + 1][p][s | dar[p]] <= 42) {
str[len] = i + 'a';
dfs(len + 1, p, s | dar[p]);
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i ++ ) insert(i);
build();
f[0][0][0] = 1;
for (int i = 0; i <= n; i ++ )
for (int j = 0; j <= idx; j ++ )
for (int s = 0; s < 1 << m; s ++ )
for (int k = 0; k < 26; k ++ ) {
int p = tr[j][k];
f[i + 1][p][s | dar[p]] += f[i][j][s];
}
i64 ans = 0;
for (int i = 0; i <= idx; i ++ ) ans += f[n][i][(1 << m) - 1];
cout << ans << endl;
if (ans <= 42) dfs(0, 0, 0);
return 0;
}