Smiling & Weeping

　　　　　　　　　　　　　　---- 自从我们相遇的那一刻，你是我白天黑夜不落的星

题目链接：Problem - 2222 (hdu.edu.cn)

题目就是一道AC自动机模板

Talk is cheap , show me the code

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cstdio>
 6 #include<queue>
 7 using namespace std;
 8 const int N = 1000005;
 9 struct node{
10     int son[26];                // 26个字母
11     int end;                    // 字符串结尾标记
12     int fail;                   // 失配指针
13 }t[N];                          // trie,字典树
14 int cnt;                        // 当前新分配的存储位置
15 void Insert(char *s){           // 在字典树上插入单词s
16     int now = 0;                // 字典树上当前匹配到的节点，从root=0开始
17     for(int i = 0; s[i]; i++){  // 逐一在字典树上查找s[]的每个字符
18         int ch = s[i]-'a';      
19         if(t[now].son[ch] == 0) // 如果这个字符还没有存过
20             t[now].son[ch] = cnt++; // 把cnt位置分配给这个字符
21         now = t[now].son[ch];       // 沿着字典树向下走
22     }
23     t[now].end++;               // end>0,它是字符串的结尾，end=0不是结尾
24 }
25 void getFail(){                 // 用BFS构建每个节点的Fail指针
26     queue<int> q;               
27     for(int i = 0; i < 26; i++) // 把第1层入队，即root的子节点
28         if(t[0].son[i])         // 这个位置有字符
29             q.push(t[0].son[i]);
30     while(!q.empty()){
31         int now = q.front();    // 队首的Fail指针已求得，下面求它孩子的的Fail指针
32         q.pop();
33         for(int i = 0; i < 26; i++){    // 遍历now的所有孩子
34             if(t[now].son[i]){          // 若这个位置有字符
35                 t[t[now].son[i]].fail = t[t[now].fail].son[i];
36                 // 这个孩子的Fail="父节点的Fail指针所指向的节点的与x同字符的子节点"
37                 q.push(t[now].son[i]);  // 这个孩子先入队，后面再处理它的孩子
38             } else {                    // 若这个位置无字符
39                 t[now].son[i] = t[t[now].fail].son[i];  // 虚拟节点，用于底层的Fail指针计算
40             }
41         }
42     }
43 }
44 int query(char *s){                     // 在文本s中找有多少个模式串
45     int ans = 0;
46     int now = 0;                        // 从 root=0 开始找
47     for(int i = 0; s[i]; i++){          // 对文本串进行遍历
48         int ch = s[i] - 'a';
49         now = t[now].son[ch];
50         int tmp = now;
51         while(tmp && t[tmp].end != -1)  // 利用Fail指针找出所有匹配的模式串
52         {
53             ans += t[tmp].end;
54             t[tmp].end = -1;            // 以这个字符为结尾的模式串已经统计，后面不需要再统计
55             tmp = t[tmp].fail;          // fail指针跳转
56             // cout << "tmp=" << t[tmp].son;
57         }
58     }
59     return ans;
60 }
61 char str[N];
62 int main()
63 {
64     int k;
65     scanf("%d",&k);
66     while(k--){
67         memset(t , 0 , sizeof(t));
68         cnt = 1;
69         int n;
70         scanf("%d",&n);
71         while(n--) { scanf("%s",str); Insert(str); }
72         getFail();
73         scanf("%s",str);
74         printf("%d\n",query(str));
75     }
76     return 0;
77 }

当上天赐给你荒野时，就意味着，他要你成为高飞的鹰

文章到此结束，外面下次再见