病毒侵袭持续中
Problem Description
小t非常感谢大家帮忙解决了他的上一个问题。然而病毒侵袭持续中。在小t的不懈努力下，他发现了网路中的“万恶之源”。这是一个庞大的病毒网站，他有着好多好多的病毒，但是这个网站包含的病毒很奇怪，这些病毒的特征码很短，而且只包含“英文大写字符”。当然小t好想好想为民除害，但是小t从来不打没有准备的战争。知己知彼，百战不殆，小t首先要做的是知道这个病毒网站特征：包含多少不同的病毒，每种病毒出现了多少次。大家能再帮帮他吗？
Input
第一行，一个整数N（1<=N<=1000），表示病毒特征码的个数。
接下来N行，每行表示一个病毒特征码，特征码字符串长度在1—50之间，并且只包含“英文大写字符”。任意两个病毒特征码，不会完全相同。
在这之后一行，表示“万恶之源”网站源码，源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符（不包括回车）。
Output
按以下格式每行一个，输出每个病毒出现次数。未出现的病毒不需要输出。
病毒特征码: 出现次数
冒号后有一个空格，按病毒特征码的输入顺序进行输出。
Sample Input
3
AA
BB
CC
ooxxCC%dAAAoen....END
Sample Output
AA: 2
CC: 1
Hint Hit：题目描述中没有被提及的所有情况都应该进行考虑。比如两个病毒特征码可能有相互包含或者有重叠的特征码段。计数策略也可一定程度上从Sample中推测。
Source
2009 Multi-University Training Contest 16 - Host by NIT
题目类型：AC自动机
算法分析：将病毒标识码插入到Trie树中，然后进行多模式匹配并使用cnt数组记录出现的模式串的个数，注意文本串中是会出现非大写字母的!! 如果不使用循环读入会WA!!!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 1e9 + 7; const int maxn = 26; const int nodemaxn = 50000 + 66; char ss[2000000+maxn]; int cnt[1000+6]; char val[1000+6][66]; struct ACNode { int next[nodemaxn][maxn], pre[nodemaxn], last[nodemaxn], id[nodemaxn]; int root, len; void Init () { len = 0; root = newnode (); } int newnode () { for (int i = 0; i < maxn; i++) next[len][i] = -1; last[len] = id[len] = 0; len++; return len - 1; } void Insert (char *s, int ff) { int p = root; for(int i = 0; s[i]; i++) { if(next[p][s[i]-'A'] == -1) next[p][s[i]-'A'] = newnode (); p = next[p][s[i]-'A']; } last[p]++; id[p] = ff; } void Build () { queue <int> qu; pre[root] = root; for(int i = 0; i < maxn; i++) { if(next[root][i] == -1) next[root][i] = root; else { pre[next[root][i]] = root; qu.push (next[root][i]); } } while (!qu.empty ()) { int p = qu.front(); qu.pop (); for (int i = 0; i < maxn; i++) { if (next[p][i] == -1) next[p][i] = next[pre[p]][i]; else { pre[next[p][i]] = next[pre[p]][i]; qu.push (next[p][i]); } } } } void Query (char *s) { int p = root; for (int i = 0; s[i]; i++) { if (s[i] < 'A' || s[i] > 'Z') p = root; else p = next[p][s[i]-'A'];//一步到位，重要!!! 当存在时走到下一层，否则回溯!!! int temp = p; while (temp != root) { if (last[temp]) { cnt[id[temp]]++; } temp = pre[temp]; } } } }; ACNode ac; int main() { // freopen ("aaa.txt", "r", stdin); int n; while (scanf ("%d", &n) != EOF) { ac.Init (); memset (cnt, 0, sizeof (cnt)); for (int i = 1; i <= n; i++) { scanf ("%s", val[i]); ac.Insert (val[i], i); } ac.Build (); gets (ss); gets (ss); ac.Query (ss); for (int i = 1; i <= n; i++) { if (cnt[i]) printf ("%s: %d\n", val[i], cnt[i]); } } return 0; } |
- « 上一篇：hdu2973
- hdu3292：下一篇 »