ZOJ 3228 AC自动机 重叠和不重叠

时间:2022-06-01 16:46:31

点击打开链接

题意:给定模式串,问下面的串最多出现多少次,0代表可以重叠,1代表不能重叠

思路:正常的0可以用模版直接实现,1的可以再写一个查询的,不能重叠,尽量先取前面,结果是最优的,所以我就记录这个串上一次出现的位置,然后在走了串这么长的长度才可以在+1.

[html] view plain copy
  1. #include <stdio.h>  
  2. #include <string.h>  
  3. #include <memory.h>  
  4. struct node{  
  5.     node *fail;  
  6.     node *next[26];  
  7.     int id;  
  8.     node(){  
  9.         fail=NULL;  
  10.         id=0;  
  11.         memset(next,NULL,sizeof(next));  
  12.     }  
  13. }*q[100000],*root;  
  14. char str1[100003][7],str2[100003];  
  15. int A[100003],cnt[100003][2],pos[100003],Len[100003],n;  
  16. void insert_Trie(char *str,int num1){  
  17.     node *p=root;  
  18.     int i=0,id;  
  19.     while(str[i]){  
  20.         id=str[i]-'a';  
  21.         if(p->next[id]==NULL) p->next[id]=new node();  
  22.         p=p->next[id];i++;  
  23.     }  
  24.     p->id=num1;  
  25. }  
  26. int search_1(char *str){  
  27.     node *p=root;  
  28.     int m,i=0;  
  29.     while(str[i]){  
  30.         m=str[i]-'a';  
  31.         if(p->next[m]==NULL) return -1;  
  32.         p=p->next[m];  
  33.         i++;  
  34.     }  
  35.     return p->id;  
  36. }  
  37. void build_ac(){  
  38.     int head=0,tail=0;  
  39.     root->fail=NULL;  
  40.     q[head++]=root;  
  41.     node *p,*temp;  
  42.     while(head!=tail){  
  43.         temp=q[tail++];  
  44.         tail%=100000;  
  45.         for(int i=0;i<26;i++){  
  46.             if(temp->next[i]!=NULL){  
  47.                 if(temp==root) temp->next[i]->fail=root;  
  48.                 else{  
  49.                     p=temp->fail;  
  50.                     while(p!=NULL){  
  51.                         if(p->next[i]!=NULL){  
  52.                             temp->next[i]->fail=p->next[i];  
  53.                             break;  
  54.                         }  
  55.                         p=p->fail;  
  56.                     }  
  57.                     if(p==NULL) temp->next[i]->fail=root;  
  58.                 }  
  59.                 q[head++]=temp->next[i];  
  60.                 head%=100000;  
  61.             }  
  62.         }  
  63.     }  
  64. }  
  65. void query(){  
  66.     int i=0;  
  67.     node *p=root,*temp;  
  68.     while(str2[i]){  
  69.         int id=str2[i]-'a';  
  70.         while(p->next[id]==NULL&&p!=root) p=p->fail;  
  71.         p=p->next[id];  
  72.         p=(p==NULL)?root:p;  
  73.         temp=p;  
  74.         while(temp!=root){  
  75.             if(temp->id){  
  76.                 cnt[temp->id][0]++;  
  77.             }  
  78.             temp=temp->fail;  
  79.         }  
  80.         i++;  
  81.     }  
  82. }  
  83. void query1(){  
  84.     int i=0;  
  85.     node *p=root,*temp;  
  86.     while(str2[i]){  
  87.         int id=str2[i]-'a';  
  88.         while(p->next[id]==NULL&&p!=root) p=p->fail;  
  89.         p=p->next[id];  
  90.         p=(p==NULL)?root:p;  
  91.         temp=p;  
  92.         while(temp!=root){  
  93.             if(temp->id&&i-pos[temp->id]>=Len[temp->id]){  
  94.                 pos[temp->id]=i;  
  95.                 cnt[temp->id][1]++;  
  96.             }  
  97.             temp=temp->fail;  
  98.         }  
  99.         i++;  
  100.     }  
  101. }  
  102. int query_num(char *str,int aa){  
  103.     int i=0;  
  104.     node *p=root;  
  105.     while(str[i]){  
  106.         int id=str[i]-'a';  
  107.         p=p->next[id];  
  108.         i++;  
  109.     }  
  110.     return cnt[p->id][aa];  
  111. }  
  112. void del(node *p){  
  113.      if(p==NULL)return ;  
  114.      for(int i=0;i<26;i++)del(p->next[i]);  
  115.      delete p;  
  116. }  
  117. int main(){  
  118.     int t=1;  
  119.     while(scanf("%s",str2)!=-1){  
  120.         scanf("%d",&n);  
  121.         root=new node();  
  122.         memset(cnt,0,sizeof(cnt));  
  123.         memset(pos,-1,sizeof(pos));  
  124.         for(int i=1;i<=n;i++){  
  125.             scanf("%d%s",&A[i],str1[i]);  
  126.             Len[i]=strlen(str1[i]);  
  127.             insert_Trie(str1[i],i);  
  128.         }  
  129.         build_ac();  
  130.         query();  
  131.         query1();  
  132.         printf("Case %d\n",t++);  
  133.         for(int i=1;i<=n;i++){  
  134.             int ttt=query_num(str1[i],A[i]);  
  135.             printf("%d\n",ttt);  
  136.         }  
  137.         printf("\n");  
  138.         del(root);  
  139.     }  
  140.     return 0;  
  141. }