AC自己主动机的模板题。须要注意的是，对于每一个字符串，须要利用map将它映射到一个结点上，这样才干按顺序输出结果。
| 14360841 | 1449 | Accepted | C++ | 0.146 | 2014-10-16 11:41:35 |
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 150 * 75;
const int len = 1111111;
const int max_size = 26;
char str[155][75];
char _str[len];
struct Trie{ //AC
int tr[maxn][max_size];
int fail[maxn];
int val[maxn]; //结果
int sz,root,_max; //出现次数
map<int,int>countx;//计算第i个字符串出现的次数
map<string,int>vis;
int index(char c){
return c - 'a';
}
int newnode(){
val[sz] = 0;
for(int i = 0; i < 26; i++) tr[sz][i] = -1;
sz ++;
return sz - 1;
}
void init(){
sz = 0;_max = 0;
root = newnode();
countx.clear();
vis.clear();
}
void insert(char *s,int id){
int u = root;
int n = strlen(s);
for(int i = 0; i < n; i++){
int c = index(s[i]);
//printf("%d %d\n",u,c);
if(tr[u][c] == -1)
tr[u][c] = newnode();
u = tr[u][c];
}
vis[string(s)] = u; //这个字符串相应的结点编号
//printf("%d\n",u);
val[u] ++;//达到这个结点的单词
}
void build(){
queue<int>q;
fail[root] = root;
for(int i = 0; i < 26; i++){
if(tr[root][i] == -1)
tr[root][i] = root;
else{
fail[tr[root][i]] = root;
q.push(tr[root][i]);
}
}
while(!q.empty()){
int now = q.front(); q.pop();
for(int i = 0; i < 26; i++){
if(tr[now][i] == -1)
tr[now][i] = tr[fail[now]][i];
else{
fail[tr[now][i]] = tr[fail[now]][i];
q.push(tr[now][i]);
}
}
}
}
void countt(char *s){
int n = strlen(s);
int u = root;
for(int i = 0; i < n; i++){
u = tr[u][index(s[i])];
int temp = u;
while(temp != root){
if(val[temp]){ //这个结点存在单词
countx[temp]++; //这个结点
_max = max(_max,countx[temp]);
}
temp = fail[temp];
}
}
}
};
Trie ac;
int main(){
int n;
while(scanf("%d",&n) && n){
ac.init();
for(int i = 0; i < n; i++){
scanf("%s",str[i]);
ac.insert(str[i],i); //插入单词
}
//printf("%d\n",ac.sz);
ac.build();
scanf("%s",_str);
ac.countt(_str);
printf("%d\n",ac._max);
for(int i = 0; i < n; i++){
if(ac.countx[ac.vis[string(str[i])]] == ac._max)
printf("%s\n",str[i]);
}
}
return 0;
}