[模板] 一些要复习的模板

  1 // Warning: There Is An Error In This Code.
  2 // When There Are Two Strings That One Is Included By The Other.
  3 // It Will Give A Wrong Answer.
  4 // By. Kimitsu Nanjo In 06.28.2018.
  5 // https://www.luogu.org/problemnew/show/P3796
  6 
  7 #include <cstdio>
  8 #include <cstdlib>
  9 #include <cstring>
 10 #include <algorithm>
 11 
 12 const int maxn = 1000000 + 10;
 13 char a[maxn], word[maxn];
 14 
 15 struct Node{
 16   int cnt;
 17   Node *fail, *next[26];
 18 }*queue[maxn], *root;
 19 
 20 inline void Refl(Node *root) {
 21   root->cnt = 0;
 22   root->fail = NULL;
 23   for(int i = 0; i < 26; ++i)
 24     root->next[i] = NULL;
 25 }
 26 
 27 inline void Insert(char *s, int len) {
 28   Node *p = root;
 29   for(int i = 0; i < len; ++i) {
 30     if( p->next[s[i] - 'a'] == NULL ) {
 31       Node *q = (Node*)malloc(sizeof(Node)); Refl(q);
 32       p->next[s[i] - 'a'] = q;
 33     }
 34     p = p->next[s[i] - 'a'];
 35   }
 36   p->cnt++;
 37 }
 38 
 39 inline void Build_fail(Node *root) {
 40   int head = 0, tail = 0;   //队列头、尾指针 
 41   queue[head++] = root;   //先将root入队 
 42   while( head != tail )
 43   {
 44     Node *p = NULL, *temp = queue[tail++];    //弹出队头结点 
 45     for(int i = 0; i < 26; ++i) {
 46       if( temp->next[i] != NULL ) {
 47             //找到实际存在的字符结点
 48             //temp->next[i] 为该结点，temp为其父结点 
 49         if( temp == root ) temp->next[i]->fail = root;
 50             //若是第一层中的字符结点，则把该结点的失败指针指向root 
 51         else {
 52               //依次回溯该节点的父节点的失败指针直到某节点的next[i]与该节点相同
 53               //则把该节点的失败指针指向该next[i]节点； 
 54               //若回溯到 root 都没有找到，则该节点的失败指针指向 root
 55           p = temp->fail;   //将该结点的父结点的失败指针给p 
 56           while( p != NULL ) {
 57             if( p->next[i] != NULL ) {
 58               temp->next[i]->fail = p->next[i];
 59               break;
 60             }
 61             p = p->fail;
 62           }
 63               //让该结点的失败指针也指向root 
 64           if( p == NULL ) temp->next[i]->fail = root;
 65         }
 66         queue[head++] = temp->next[i];
 67             //每处理一个结点，都让该结点的所有孩子依次入队 
 68       }
 69     }
 70   }
 71 }
 72 
 73 inline int Querry(Node *root, int len) {    //i为主串指针，p为模式串指针 
 74   int ans = 0;
 75   Node *p = root;
 76   for(int i = 0; i < len; ++i) {
 77         //由失败指针回溯查找，判断s[i]是否存在于Trie树中 
 78     while( p->next[a[i] - 'a'] == NULL && p != root ) p = p->fail;
 79     p = p->next[a[i] - 'a'];    //找到后p指针指向该结点 
 80     if( p == NULL ) p = root;   //若指针返回为空，则没有找到与之匹配的字符 
 81     Node *temp = p;   //匹配该结点后，沿其失败指针回溯，判断其它结点是否匹配 
 82     while( temp != root ) {   //匹配结束控制 
 83       if( temp->cnt >= 0 )   //判断该结点是否被访问 
 84         ans += temp->cnt, temp->cnt = -1;
 85           //由于cnt初始化为 0，所以只有cnt>0时才统计了单词的个数, 标记已访问过 
 86       temp = temp->fail;    //回溯 失败指针 继续寻找下一个满足条件的结点 
 87     }
 88   }
 89   return ans;
 90 }
 91 
 92 void Free_Node(Node *p) {
 93   for(int i = 0; i < 26; ++i)
 94     if( p->next[i] != NULL ) Free_Node(p->next[i]);
 95   free(p);
 96 }
 97 
 98 int main(int argc, char* const argv[])
 99 {
100   int n = 0;
101   root = (struct Node*)malloc(sizeof(Node)), Refl(root);
102   scanf("%d", &n);
103   for(int i = 1; i <= n; ++i) {
104     scanf("%s", word);
105     Insert(word, strlen(word));
106   }
107   Build_fail(root);
108   scanf("%s", a);
109   printf("%d
", Querry(root, strlen(a)));
110 
111   return 0;
112 }