uvalive 4670 Dominating Patterns

在文本串中找出现次数最多的子串。
思路：AC自动机模板+修改一下print函数。
  1 #include<stdio.h>
  2 #include<math.h>
  3 #include<stdio.h>
  4 #include<stdlib.h>
  5 #include<iostream>
  6 #include<string>
  7 #include<memory.h>
  8 #include<map>
  9 #include<queue>
 10 using namespace std;
 11 const int SIGMA_SIZE = 26;
 12 const int MAXNODE = 11000;
 13 const int MAXS = 150 + 10;
 14 
 15 map<string,int> ms;
 16 
 17 struct AhoCorasickAutomata
 18 {
 19     int ch[MAXNODE][SIGMA_SIZE];
 20     int f[MAXNODE];    // fail函数
 21     int val[MAXNODE];  // 每个字符串的结尾结点都有一个非0的val
 22     int last[MAXNODE]; // 输出链表的下一个结点
 23     int cnt[MAXS];
 24     int sz;
 25 
 26     void init()
 27     {
 28         sz = 1;
 29         memset(ch[0], 0, sizeof(ch[0]));
 30         memset(cnt, 0, sizeof(cnt));
 31         ms.clear();
 32     }
 33 
 34     // 字符c的编号
 35     int idx(char c)
 36     {
 37         return c-'a';
 38     }
 39 
 40     // 插入字符串。v必须非0
 41     void insert(char *s, int v)
 42     {
 43         int u = 0, n = strlen(s);
 44         for(int i = 0; i < n; i++)
 45         {
 46             int c = idx(s[i]);
 47             if(!ch[u][c])
 48             {
 49                 memset(ch[sz], 0, sizeof(ch[sz]));
 50                 val[sz] = 0;
 51                 ch[u][c] = sz++;
 52             }
 53             u = ch[u][c];
 54         }
 55         val[u] = v;
 56         ms[string(s)] = v;
 57     }
 58 
 59     // 递归打印以结点j结尾的所有字符串
 60     void print(int j)
 61     {
 62         if(j)
 63         {
 64             cnt[val[j]]++;
 65             print(last[j]);
 66         }
 67     }
 68 
 69     // 在T中找模板
 70     int find(char* T)
 71     {
 72         int n = strlen(T);
 73         int j = 0; // 当前结点编号，初始为根结点
 74         for(int i = 0; i < n; i++)   // 文本串当前指针
 75         {
 76             int c = idx(T[i]);
 77             while(j && !ch[j][c]) j = f[j]; // 顺着细边走，直到可以匹配
 78             j = ch[j][c];
 79             if(val[j]) print(j);
 80             else if(last[j]) print(last[j]); // 找到了！
 81         }
 82     }
 83 
 84     // 计算fail函数
 85     void getFail()
 86     {
 87         queue<int> q;
 88         f[0] = 0;
 89         // 初始化队列
 90         for(int c = 0; c < SIGMA_SIZE; c++)
 91         {
 92             int u = ch[0][c];
 93             if(u)
 94             {
 95                 f[u] = 0;
 96                 q.push(u);
 97                 last[u] = 0;
 98             }
 99         }
100         // 按BFS顺序计算fail
101         while(!q.empty())
102         {
103             int r = q.front();
104             q.pop();
105             for(int c = 0; c < SIGMA_SIZE; c++)
106             {
107                 int u = ch[r][c];
108                 if(!u) continue;
109                 q.push(u);
110                 int v = f[r];
111                 while(v && !ch[v][c]) v = f[v];
112                 f[u] = ch[v][c];
113                 last[u] = val[f[u]] ? f[u] : last[f[u]];
114             }
115         }
116     }
117 
118 };
119 
120 AhoCorasickAutomata ac;
121 char text[1000001], p[151][80];
122 int n, T;
123 
124 
125 int main()
126 {
127     while(scanf("%d",&n)==1&&n)
128     {
129         ac.init();
130         for(int i=1; i<=n; i++)
131         {
132             scanf("%s",p[i]);
133             ac.insert(p[i],i);
134         }
135         ac.getFail();
136         scanf("%s",text);
137         ac.find(text);
138         int best=-1;
139         for(int i=1; i<=n; i++)
140         {
141             if(ac.cnt[i]>best)
142                 best=ac.cnt[i];
143         }
144         printf("%d
",best);
145         for(int i=1; i<=n; i++)
146         {
147             if(ac.cnt[ms[string(p[i])]]==best)
148             {
149                 printf("%s
",p[i]);
150             }
151         }
152     }
153     return 0;
154 }
View Code