题目描述
有个由小写字母组成的模式串以及一个文本串
。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串
中出现的次数最多。
输入输出格式
输入格式：
输入含多组数据。
每组数据的第一行为一个正整数，表示共有
个模式串，
。
接下去行，每行一个长度小于等于
的模式串。下一行是一个长度小于等于
的文本串
。
输入结束标志为。
输出格式：
对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。
输入输出样例
输入样例#1：
2 aba bab ababababac 6 beta alpha haha delta dede tata dedeltalphahahahototatalpha 0
输出样例#1：
4 aba 2 alpha haha
解法1：。。。。。。。。8813ms
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; struct Tree{int fail,vis[26],end;}AC[100000];//Trie tree //vis:son_points' position //end:mark the word_number end with this point int cnt=0;//Trie's pointer struct Result{int num,pos;}Ans[100000];//mark every word's appear_times bool operator <(Result a,Result b){if(a.num!=b.num)return a.num>b.num;else return a.pos<b.pos;}//operate the < operation //if it's appear_times higher.just return it,or just return the one have lower pos string s[100000]; inline void Clean(int x){memset(AC[x].vis,0,sizeof(AC[x].vis));AC[x].fail=0;AC[x].end=0;} //initialization inline void Build(string s,int Num){ int l=s.length(),now=0;//l:mark the length,now:mark the now_position for(int i=0;i<l;++i)//make Trie_tree {// if the Trie tree has not this point if(AC[now].vis[s[i]-'a']==0)AC[now].vis[s[i]-'a']=++cnt,Clean(cnt); //if has not been visited ,just go on //add it to now's son_points and then initialization it now=AC[now].vis[s[i]-'a'];//just run to next level }AC[now].end=Num;//mark the end } void Get_fail()//make fail {queue<int> Q;//set a queue for(int i=0;i<26;++i)if(AC[0].vis[i]!=0)//if it has not been visited AC[AC[0].vis[i]].fail=0,Q.push(AC[0].vis[i]); //just point it to the root_point and then push it to the queue while(!Q.empty())//BFS to ask for fail {int u=Q.front();Q.pop();//use u to mark the queue_head,and then push it out for(int i=0;i<26;++i) if(AC[u].vis[i]!=0)//it it has been visited,just it is real AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i],Q.push(AC[u].vis[i]); //make it's son_point's fail against now_fail_son(renew) //and then push then son_point to the queue else AC[u].vis[i]=AC[AC[u].fail].vis[i]; //or ,this point has not been visited //just it is not real //just use it's fail(spare tire) } } int AC_Query(string s){int l=s.length(),now=0,ans=0; for(int i=0;i<l;++i){ now=AC[now].vis[s[i]-'a']; for(int t=now;t;t=AC[t].fail)Ans[AC[t].end].num++; }return ans; } int main(){int n; while(1){scanf("%d",&n);if(n==0)break;cnt=0;Clean(0); for(int i=1;i<=n;++i)cin>>s[i],Ans[i].num=0,Ans[i].pos=i,Build(s[i],i); //read every given_part(key),initialization it AC[0].fail=0;Get_fail(); //initialization root's fail and want fail cin>>s[0];AC_Query(s[0]); //read the given_long_word and ask for the ans sort(&Ans[1],&Ans[n+1]);printf("%d ",Ans[1].num); //sort the ans and printf the biggest solution cout<<s[Ans[1].pos]<<endl;//give the appear_most_often_word for(int i=2;i<=n;++i)if(Ans[i].num==Ans[i-1].num)cout<<s[Ans[i].pos]<<endl;else break; //then if have more than one solution, just printf them //after sort ,the appear_most_often_word must be in the front //and the Ans[1] has printf just start from 2 //if it is not the best solution,it means there is no best solution any more,just break }return 0; }//this program's speed is very slow,can only accept just in time //maybe we should search for a better solution
虽然实现的很自然，但是这效率。。。。。。光荣地拿到了luogu rank 倒数第一
能有更好的解法吗？
自然是有的。
解法2：1688ms最慢点464ms
无注解，清新模板版
#include<queue> #include<cstdio> #include<cstring> #define maxn 15000 #define maxc 1000005 #define For(a,b,c) for(a=b;a<=(int)(c);++a) using namespace std; int n; char T[maxc],P[151][71]; inline int idx(char c){return c-'a';} struct Trie{int sz,ch[maxn][26],val[maxn]; inline void init(){sz=0;memset(ch,0,sizeof(ch));memset(val,0,sizeof(val));} inline void insert(char *s,int v){ int i,u=0,l=strlen(s); For(i,0,l-1){int c=idx(s[i]); if(!ch[u][c])ch[u][c]=++sz;u=ch[u][c]; }val[u]=v;} }tr; struct AC_machine{int fail[maxn],last[maxn],cnt[maxn]; inline void init(){memset(fail,0,sizeof(fail));memset(last,0,sizeof(last));memset(cnt,0,sizeof(cnt));} inline void getfail(){int c,u,k,r;queue<int>q;fail[0]=0; For(c,0,25)if(tr.ch[0][c])q.push(tr.ch[0][c]); while(!q.empty()){r=q.front(),q.pop(); For(c,0,25){u=tr.ch[r][c]; if(!u){tr.ch[r][c]=tr.ch[fail[r]][c];continue;}q.push(u); k=fail[r];while(k&&!tr.ch[k][c])k=fail[k]; fail[u]=tr.ch[k][c]; last[u]=tr.val[fail[u]]?fail[u]:last[fail[u]]; }}} inline void calc(int x){while(x)++cnt[tr.val[x]],x=last[x];} inline void find(char *s){int i,j,l=strlen(s); For(i,0,l-1){j=tr.ch[j][idx(s[i])]; if(tr.val[j])calc(j); else if(last[j]) calc(last[j]);}} }ac; int main(){int i; while(scanf("%d",&n),n){tr.init();ac.init(); For(i,1,n)scanf("%s",P[i]),tr.insert(P[i],i); scanf("%s",T);ac.getfail();ac.find(T); int best=-1; For(i,1,n) if(ac.cnt[i]>best) best=ac.cnt[i]; printf("%d ",best); For(i,1,n)if(ac.cnt[i]==best)printf("%s ",P[i]); }return 0;}