HDU 2896 病毒侵袭——AC自动机

HDU 2896 病毒侵袭——AC自动机

数组开小了却提示TLE。。。真讨厌

#include #include #include #include #include using namespace std;const int MAXN = 1e5 + 10;const int MAXL = 1e4 + 10;const int SIZE = 128;char str[MAXL];int N, M;struct AC { int total, val[MAXN], fail[MAXN], child[MAXN][SIZE]; void init() { total = 1; memset(val, 0, sizeof(val)); memset(fail, 0, sizeof(fail)); memset(child[0], 0, sizeof(child[0])); } void Insert(char *P, int id) { int len = strlen(P), root = 0; for (int i = 0; i < len; i++) { if (!child[root][P[i]]) { memset(child[total], 0, sizeof(child[total])); child[root][P[i]] = total++; } root = child[root][P[i]]; } val[root] = id; } void Getfail() { queue q; for (int i = 0; i < SIZE; i++) { if (child[0][i]) q.push(child[0][i]); } while (!q.empty()) { int root = q.front(); q.pop(); for (int i = 0; i < SIZE; i++) { int u = child[root][i]; if (!u) { child[root][i] = child[fail[root]][i]; continue; } q.push(u); int v = fail[root]; while (v && !child[v][i]) v = fail[v]; fail[u] = child[v][i]; } } } bool Search(char *T, int id) { bool ok = false; int len = strlen(T), root = 0, temp; int cnt = 0, ans[10], vis[1000] = {0}; for (int i = 0; i < len; i++) { temp = root = child[root][T[i]]; while (temp && val[temp]) { if (!vis[val[temp]]) { vis[val[temp]] = 1; ans[cnt++] = val[temp]; ok = true; } if (cnt == 3) break; temp = fail[temp]; } } if (ok) { printf("web %d:", id); sort(ans, ans + cnt); for (int i = 0; i < cnt; i++) { printf(" %d", ans[i]); } printf("\n"); } return ok; }}ac;int main() { ac.init(); scanf("%d", &N); for (int i = 1; i <= N; i++) { scanf("%s", str); ac.Insert(str, i); } ac.Getfail(); int sum = 0; scanf("%d", &M); for (int i = 1; i <= M; i++) { scanf("%s", str); if (ac.Search(str, i)) sum++; } printf("total: %d\n", sum);}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。