首页 > 代码库 > HDU - 3065 病毒侵袭持续中
HDU - 3065 病毒侵袭持续中
Description
小t非常感谢大家帮忙解决了他的上一个问题。然而病毒侵袭持续中。在小t的不懈努力下,他发现了网路中的“万恶之源”。这是一个庞大的病毒网站,他有着好多好多的病毒,但是这个网站包含的病毒很奇怪,这些病毒的特征码很短,而且只包含“英文大写字符”。当然小t好想好想为民除害,但是小t从来不打没有准备的战争。知己知彼,百战不殆,小t首先要做的是知道这个病毒网站特征:包含多少不同的病毒,每种病毒出现了多少次。大家能再帮帮他吗?
Input
第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。
接下来N行,每行表示一个病毒特征码,特征码字符串长度在1―50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。
在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。
接下来N行,每行表示一个病毒特征码,特征码字符串长度在1―50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。
在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。
Output
按以下格式每行一个,输出每个病毒出现次数。未出现的病毒不需要输出。
病毒特征码: 出现次数
冒号后有一个空格,按病毒特征码的输入顺序进行输出。
病毒特征码: 出现次数
冒号后有一个空格,按病毒特征码的输入顺序进行输出。
Sample Input
3 AA BB CC ooxxCC%dAAAoen....END
Sample Output
AA: 2 CC: 1 思路:AC自动机,加了个数组标记个数,新的模板#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int maxn = 1010; char str[maxn][maxn]; struct Trie { int next[1010*50][128], fail[1010*50], end[1010*50]; int root, L; int newNode() { for (int i = 0; i < 128; i++) next[L][i] = -1; end[L++] = -1; return L-1; } void init() { L = 0; root = newNode(); } void insert(char s[], int id) { int len = strlen(s); int now = root; for (int i = 0; i < len; i++) { if (next[now][s[i]] == -1) next[now][s[i]] = newNode(); now = next[now][s[i]]; } end[now] = id; } void build() { queue<int> Q; fail[root] = root; for (int i = 0; i < 128; i++) if (next[root][i] == -1) next[root][i] = root; else { fail[next[root][i]] = root; Q.push(next[root][i]); } while (!Q.empty()) { int now = Q.front(); Q.pop(); for (int i = 0; i < 128; i++) if (next[now][i] == -1) next[now][i] = next[fail[now]][i]; else { fail[next[now][i]] = next[fail[now]][i]; Q.push(next[now][i]); } } } int num[1010]; void query(char buf[], int n) { for (int i = 0; i < n; i++) num[i] = 0; int len = strlen(buf); int now = root; for (int i = 0; i < len; i++) { now = next[now][buf[i]]; int temp = now; while (temp != root) { if (end[temp] != -1) num[end[temp]]++; temp = fail[temp]; } } for (int i = 0; i < n; i++) if (num[i]) printf("%s: %d\n", str[i], num[i]); } } ac; char buf[2000010]; int main() { int n; while (scanf("%d", &n) != EOF) { ac.init(); for (int i = 0; i < n; i++) { scanf("%s", str[i]); ac.insert(str[i], i); } ac.build(); scanf("%s", buf); ac.query(buf, n); } return 0; }
HDU - 3065 病毒侵袭持续中
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。