LA 4670 所有出现最多次的模式串 AC自动机

题意：

给定n个模式串

第n+1行给定文本串

问：

在文本串出现最多次的模式串 出现的次数和所有出现最多次的模式串（按字典序输出）

思路：

AC自动机模版题

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; #define N 1000010 #define maxnode 250001 #define sigma_size 26 struct node{ char ch[80]; }ans[200]; int top; struct Trie{ int ch[maxnode][sigma_size]; int val[maxnode]; int last[maxnode]; int f[maxnode]; int num[maxnode]; int pre[maxnode]; int len[maxnode]; int Char[maxnode]; int sz; void init(){ sz=1; memset(ch,0,sizeof(ch)); memset(val, 0, sizeof(val)); memset(f,0,sizeof(f)); memset(last,0,sizeof(last)); //记录该节点前一个节点是谁 memset(len, 0, sizeof(len)); } int idx(char c){ return c-'a'; } void print(int j, char *s){ s[len[j]] = 0; while(j){ s[len[j]-1] = Char[j]; j = pre[j]; } } int insert(char *s){ int u = 0; for(int i = 0; s[i] ;i++){ int c = idx(s[i]); if(!ch[u][c]) ch[u][c] = sz++; pre[ch[u][c]] = u; Char[ch[u][c]] = s[i]; len[ch[u][c]] = len[u]+1; u = ch[u][c]; } val[u] ++; num[u] = 0; return u; } void getFail(){ queue
        
          q; for(int i = 0; i
         
          q; int best = 0; for(int i = 0; i < sigma_size; i++) { if(ch[0][i])q.push(ch[0][i]); if(val[ch[0][i]])best = max(best, num[ch[0][i]]); } while(!q.empty()) { int r = q.front(); q.pop(); for(int c = 0; c < sigma_size; c++){ int u = ch[r][c]; if(!u)continue; q.push(u); if(val[u])best = max(best, num[u]); } } return best; } void match(int best){ queue
          
           q; for(int i = 0; i < sigma_size; i++) { if(ch[0][i])q.push(ch[0][i]); if(val[ch[0][i]] && num[ch[0][i]]==best)print(ch[0][i], ans[top++].ch); } while(!q.empty()) { int r = q.front(); q.pop(); for(int c = 0; c < sigma_size; c++){ int u = ch[r][c]; if(!u)continue; q.push(u); if(val[u] && num[u] == best)print(u, ans[top++].ch); } } } }; Trie ac; char s[1000006]; bool cmp(node a,node b){return strcmp(a.ch, b.ch)<0;} int main(){ int n, i; while(scanf(%d,&n), n){ ac.init(); for(i = 0; i < n; i++)scanf(%s, s), ac.insert(s); ac.getFail(); scanf(%s, s); ac.find(s); int best = ac.bestnum(); printf(%d , best); top=0; ac.match(best); sort(ans, ans+top, cmp); for(i = 0; i < top; i++)printf(%s , ans[i].ch); } return 0; }