- 1#include 2#include 3#include 4#include 5#include 6 using namespace std;
- 7 int t,
- n,
- num;
- 8 int len,
- val,
- j;
- 9 char s[1000010];
- 10 struct data {
- 11 int ch[30];
- 12 int fail,
- cnt; //cnt 以该节点结束的词的个数
- 13
- }
- tree[1000010];
- 14 queue < int > q;
- 15 void clear(int x) {
- 16 memset(tree[x].ch, 0, sizeof(tree[x].ch));
- 17 tree[x].fail = 0;
- 18 tree[x].cnt = 0;
- 19
- }
- 20 void trie(int x) {
- 21 len = strlen(s);
- 22
- for (int i = 0; i) {
- 23 val = s[i] - 'a' + 1;
- 24
- if (!tree[x].ch[val]) {
- 25 num++;
- 26 clear(num);
- 27 tree[x].ch[val] = num;
- 28
- }
- 29 x = tree[x].ch[val];
- 30
- }
- 31 tree[x].cnt++;
- 32
- }
- 33 void build() {
- 34
- while (!q.empty()) q.pop();
- 35
- for (int i = 1; i <= 26; i++) 36
- if (tree[0].ch[i]) q.push(tree[0].ch[i]);
- 37
- while (!q.empty()) {
- 38 int p = q.front();
- 39 q.pop();
- 40
- for (int i = 1; i <= 26; i++) {
- 41 int fail = tree[p].fail;
- 42
- if (tree[p].ch[i]) {
- 43 44 tree[tree[p].ch[i]].fail = tree[fail].ch[i];
- 45 q.push(tree[p].ch[i]);
- 46
- }
- 47
- else tree[p].ch[i] = tree[fail].ch[i];
- 48
- }
- 49
- }
- 50
- }
- 51 int find(int x) {
- 52 int ans = 0;
- 53 len = strlen(s);
- 54
- for (int i = 0; i) {
- 55 val = s[i] - 'a' + 1;
- 56
- while (x && !tree[x].ch[val]) x = tree[x].fail;
- 57 x = tree[x].ch[val];
- 58 j = x;
- 59
- while (j && tree[j].cnt != -1) {
- 60 ans += tree[j].cnt;
- 61 tree[j].cnt = -1;
- 62 j = tree[j].fail;
- 63
- }
- 64
- }
- 65
- return ans;
- 66
- }
- 67 int main() {
- 68 scanf("%d", &t);
- 69
- while (t) {
- 70 t--;
- 71 num = 0;
- 72 clear(0);
- 73 scanf("%d", &n);
- 74
- for (int i = 1; i <= n; i++) {
- 75 scanf("%s", s);
- 76 trie(0);
- 77
- }
- 78 build();
- 79 scanf("%s", s);
- 80 printf("%d\n", find(0));
- 81
- }
- 82
- return 0;
- 83
- }
来源: http://www.bubuko.com/infodetail-2092845.html