首页 > 代码库 > UVA 1076 - Password Suspects(AC自动机+DP)
UVA 1076 - Password Suspects(AC自动机+DP)
UVA 1076 - Password Suspects
题目链接
题意:一个密码,给定m个已知子串,求这个密码最多有几种表示方式,如果小于42种,就输出这些密码
思路:先利用已有子串构造AC自动机,需要改造一下的地方是每个叶子结点为(1<<i),然后构造next数组,在状态图上进行dp,dp[i][j][k]表示在结点i,长度j,已有子串集合为k的种数,进行状态转移即可,最后判断一下答案是否不大于42,如果是再根据之前求出的dp状态去进行输出即可
代码:
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <map> #include <queue> using namespace std; typedef long long ll; const int MAXNODE = 105; const int SIGMA_SIZE = 26; const int N = 30; const int M = (1<<10) + 5; int n, m; struct AutoMac { int ch[MAXNODE][SIGMA_SIZE]; int val[MAXNODE]; int next[MAXNODE]; int last[MAXNODE]; ll dp[MAXNODE][N][M]; int out[N]; int sz; void init() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); } int idx(char c) { return c - 'a'; } void insert(char *str, int v) { int n = strlen(str); int u = 0; for (int i = 0; i < n; i++) { int c = idx(str[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 getnext() { queue<int> Q; next[0] = 0; for (int c = 0; c < SIGMA_SIZE; c++) { int u = ch[0][c]; if (u) {next[u] = 0; Q.push(u); last[u] = 0;} } while (!Q.empty()) { int r = Q.front(); Q.pop(); for (int c = 0; c < SIGMA_SIZE; c++) { int u = ch[r][c]; if (!u) { ch[r][c] = ch[next[r]][c]; continue; } Q.push(u); int v = next[r]; while (v && !ch[v][c]) v = next[v]; next[u] = ch[v][c]; val[u] |= val[next[u]]; //last[u] = val[next[u]] ? next[u] : last[next[u]]; } } } /* void print(int i, int j) { if (j) { //printf("%d: %d\n", i, val[j]); print(i, last[j]); } } void find(char *T) { int n = strlen(T); int j = 0; for (int i = 0; i < n; i++) { int c = idx(T[i]); j = ch[j][c]; if (val[j]) print(i, j); else if (last[j]) print(i, last[j]); } }*/ ll dfs(int now, int len, int st) { ll &ans = dp[now][len][st]; if (ans != -1) return ans; ans = 0; if (len == n) { if (st == (1<<m) - 1) return ans = 1; return ans = 0; } for (int i = 0; i < SIGMA_SIZE; i++) ans += dfs(ch[now][i], len + 1, st|val[ch[now][i]]); return ans; } void print(int now, int len, int st) { if (len == n) { for (int i = 0; i < len ;i++) printf("%c", out[i] + 'a'); printf("\n"); return; } for (int i = 0; i < SIGMA_SIZE; i++) { if (dp[ch[now][i]][len + 1][st|val[ch[now][i]]] > 0) { out[len] = i; print(ch[now][i], len + 1, st|val[ch[now][i]]); } } } void solve() { char str[15]; for (int i = 0; i < m; i++) { scanf("%s", str); insert(str, i); } getnext(); memset(dp, -1, sizeof(dp)); ll ans = dfs(0, 0, 0); printf("%lld suspects\n", ans); if (ans <= 42) print(0, 0, 0); } } gao; int main() { int cas = 0; while (~scanf("%d%d", &n, &m) && n || m) { printf("Case %d: ", ++cas); gao.init(); gao.solve(); } return 0; }
UVA 1076 - Password Suspects(AC自动机+DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。