[BZOj]1559 [JSOI2009] 密码 AC自动机 + 状压DP

Description

Input

Output

Sample Input

Sample Output

HINT

Source

　　好久没做过AC自动机... 感觉AC自动机主要考察的就是AC自动机上DP或者fail树上搞数据结构?

　　首先这道题是字符串， 其次还要构造包含所有串的一个串... 这样的匹配会自然而然的想到字符串里的自动机以来识别， 匹配. 要统计方案数的话， 方案数又在longlong范围内， 那就是很大咯? 那么说明除了数学计数就是DP统计嘛. 数学计数什么的想了一下情况多而且极不好做... 当然是考虑DP啦. 看一下数据范围可以想到状压. 而这种包含匹配一般是用AC自动机来完成... 那么AC自动机上状压DP这个思路就想出来咯.

　　设f[i][j][k]表示走了L步走到j节点， k是一个二进制状态表示哪些串已经被包含了.  这样转移显然， 而且答案很好统计, 就是所有的f[L][j][(1 << n) -1]. 当然由AC自动机可以转移到fail， 为了方便转移， 我们当然还是用补全AC自动机啦.

　　实际上这道题难就难在输出方案上， 毕竟DP比较naive. 想了半天没怎么想出来. 看了网上的某一种做法. 我们可以注意到只输出不超过42， 这个东西肯定很悬疑啊... 我们想我们最不好处理的就是包含完所有串之后填充L的随机数字, 要是没有这个随机数字就好了... 要是有一个随机数字的话， 他可以是26个字母之一， 无论要包含多少串， 这个数字至少都可以前后放， 那么就有26 * 2种>42. 这就很nice， 这说明要输出方案的话就不会存在随机数字.

　　同时这也说明相邻字符串要紧凑， 比如aba和ac要成abac而不是abaac. 因为如果abaac可以的话， 那么abac就可以， 这就流出空位给随机数字了. 所以可以预处理出两个字符串紧凑在一起是什么样， 然后枚举这10个字符串的排列， 每次判断紧凑排列之后长度是不是L即可， 排列是10!所以说复杂度不会爆.  不过wys跟我说实际上可以通过dp转移倒推， 于是我选择了wys的方案...

　　注意要去重和包含关系.  

#include<bits/stdc++.h>
using namespace std;
queue<int> q;
bool wr[15];
long long ans;
int n, m, tot, num, cnt, lim, L;
char str[15][15], anstr[44][30], chars[100];
int isend[110], c[110][30], wh[110], fail[110], id[110];
long long f[27][110][1 << 11];
inline void insert(char *ss) {int p = 0;for (int i = 0; ss[i]; ++ i) {int index = ss[i] - 'a';if (!c[p][index]) c[p][index] = ++ tot, wh[tot] = index;p = c[p][index];}isend[p] = ++ cnt;
}
inline bool inside(char *s1, char *s2) {int len1 = strlen(s1), len2 = strlen(s2);if (len1 < len2) return false;for (int i = 0, j, tmp; i < len1; ++ i) {for (j = 0, tmp = i ;j < len2 && tmp < len1; ++ j, ++ tmp)if (s1[tmp] != s2[j]) break;if (j == len2) return true;}return false;
}
inline void prework() {for (int i = 1; i <= m; ++ i)for (int j = 1; j <= m; ++ j) {if (i == j) continue;if (!strcmp(str[i], str[j])) wr[max(i, j)] = true;else if (inside(str[i], str[j])) wr[j] = true;}for (int i = 1; i <= m; ++ i)if (!wr[i]) {++ n;for (int j = 0; j < 11; ++ j) str[n][j] = str[i][j];}for (int i = 1; i <= n; ++ i) insert(str[i]);
}
inline void build_fail() {for (int i = 0; i < 26; ++ i)if (c[0][i]) q.push(c[0][i]);while (!q.empty()) {int u = q.front(); q.pop();for (int i = 0; i < 26; ++ i) {if (c[u][i]) {fail[c[u][i]] = c[fail[u]][i];q.push(c[u][i]);} else c[u][i] = c[fail[u]][i];}}
}
inline void dp() {f[0][0][0] = 1;lim = 1 << n;for (int i = 0; i < L; ++ i)for (int j = 0; j <= tot; ++ j)for (int k = 0; k < lim; ++ k) {if (!f[i][j][k]) continue;for (int s = 0, who; s < 26; ++ s) {who = (isend[c[j][s]]) ? (1 << (isend[c[j][s]] - 1)) : 0;f[i + 1][c[j][s]][k | who] += f[i][j][k];}}
}
void dfs(int now, int state, int res) {if (!res) {num ++;for (int i = 0; i < L; ++ i)anstr[num][i] = chars[i];anstr[num][L] = 0;// then it can printf("%s, ...)return;}chars[res - 1] = wh[now] + 'a';int x = (isend[now]) ? (1 << (isend[now] - 1)) : 0;for (int i = 0; i <= tot; ++ i)if (f[res - 1][i][state ^ x] && c[i][wh[now]] == now)dfs(i, state ^ x, res - 1);
}
inline bool cmp(const int &x, const int &y) {for (int i = 0; i < L; ++ i)if (anstr[x][i] != anstr[y][i])return anstr[x][i] < anstr[y][i];return false;
}
inline void solve() {for (int i = 0; i <= tot; ++ i)if (f[L][i][lim - 1])ans += f[L][i][lim - 1];printf("%lld\n", ans);if (ans > 42) return;for (int i = 0; i <= tot; ++ i)if (f[L][i][lim - 1]) dfs(i, lim - 1, L);for (int i = 1; i <= ans; ++ i) id[i] = i;sort(id + 1, id + ans + 1, cmp);for (int i = 1; i <= ans; ++ i)printf("%s\n", anstr[id[i]]);
}
int main() {scanf("%d%d", &L, &m);for (int i = 1; i <= m; ++ i) scanf("%s", str[i]);prework(), build_fail(), dp(), solve();return 0;
}