Keywords Search
Problem Description
In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.
Wiskey also wants to bring this feature to his image retrieval system.
Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched.
To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.
Input
First line will contain one integer means how many cases will follow by.
Each case will contain two integers N means the number of keywords and N keywords follow. (N <= 10000)
Each keyword will only contains characters 'a'-'z', and the length will be not longer than 50.
The last line is the description, and the length will be not longer than 1000000.
Output
Print how many keywords are contained in the description.
Sample Input
1
5
she
he
say
shr
her
yasherhs
Sample Output
3
Author
Wiskey
题目类型：AC自动机
算法分析：直接将按照单词建立一个AC自动机，然后如果找到一个匹配的模式串，则不断寻找这个模式串的后缀，看能不能又找到一个匹配的模式串，防止漏解。注意使用G++会MLE！！！
|
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 171 172 173 174 175 176 177 178 179 180 181 182 183 184 |
#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; char ss[1000000+maxn]; struct Node { Node *next[maxn]; Node *pre; int last; Node () { memset (next, 0, sizeof (next)); pre = 0, last = 0; } }; Node *root; void Init () { root = new Node; } void Insert (char *s) { if (!s[0]) return ; Node *p = root; for (int i = 0; s[i]; i++) { if (!p -> next[s[i]-'a']) p -> next[s[i]-'a'] = new Node; p = p -> next[s[i]-'a']; } p -> last++; } void Build () { queue <Node*> qu; Node *p = root; for (int i = 0; i < maxn; i++) if (p -> next[i]) { Node *pp = p -> next[i]; pp -> pre = root; qu.push (pp); } while (!qu.empty ()) { Node *temp = qu.front (); qu.pop (); for (int i = 0; i < maxn; i++) { Node *pp = temp -> next[i]; if (pp) { Node *par = temp -> pre; do { if (par -> next[i]) { pp -> pre = par -> next[i]; break; } else par = par -> pre; } while (par); if (!par) pp -> pre = root; qu.push (pp); } } } } int Query (char *s) { if (!s[0]) return 0; Node *p = root; int cnt = 0; for (int i = 0; s[i]; i++) { while (p != root && !p -> next[s[i]-'a']) p = p -> pre; p = p -> next[s[i]-'a']; if (!p) p = root; Node *pp = p; while (pp != root && pp -> last != -1) { cnt += pp -> last; pp -> last = -1; pp = pp -> pre; } } return cnt; } void DelTree (Node *s) { if (!s) return ; for (int i = 0; i < maxn; i++) { if (s -> next[i]) DelTree (s -> next[i]); } delete s; } int main() { // freopen ("aaa.txt", "r", stdin); int t; scanf ("%d", &t); while (t--) { int n; scanf ("%d",&n); Init (); for (int i = 1; i <= n; i++) { scanf ("%s", ss); Insert (ss); } gets (ss); gets (ss); Build (); printf ("%d\n", Query (ss)); DelTree (root); } return 0; } |
- « 上一篇：hdu2191
- hdu2521：下一篇 »