题意：统计出现次数最多的字符串，按照输入顺序输出这些字符串
#include <bits/stdc++.h> using namespace std; typedef int LL; const LL maxn = 500000 + 100; LL re = -1,ma[maxn],ccnt[maxn]; void init(){ memset( ccnt,0,sizeof( ccnt ) ); } struct ac{ LL ch[maxn][30],fail[maxn],last[maxn],val[maxn],tot; void init(){ tot = 0; memset( ch,0,sizeof( ch ) ); memset( val,0,sizeof( val ) ); } void Insert( char * str,LL i ){ LL p = 0; LL len = strlen( str ); for( LL i = 0;i < len;i++ ){ LL c = str[i] - 'a'; if( !ch[p][c] ) ch[p][c] = ++tot; p = ch[p][c]; } ma[i] = p; val[p] = 1; } queue<LL> que; void Build(){ for( LL c = 0;c < 26;c++ ){ LL x = ch[0][c]; if( !x ) continue; fail[x] = 0; que.push( x ); last[x] = 0; } while( que.size() ){ LL x = que.front(); que.pop(); for( LL c = 0;c < 26;c++ ){ LL y = ch[x][c]; if( !y ){ LL p = fail[x]; while( p && ch[ p ][c] == 0 ) p = fail[p]; ch[x][c] = ch[p][c]; continue; } que.push( y ); LL p = fail[x]; while( p && ch[ p ][c] == 0 ) p = fail[p]; fail[y] = ch[p][c]; last[y] = val[ fail[y] ] ? fail[y] : last[ fail[y] ]; } } } void Find( char* str ){ LL cnt = 0,p = 0; LL len = strlen( str ); for( LL i = 0;i< len;i++ ){ LL c = str[i] - 'a'; p = ch[p][c]; if( val[p] ) { ccnt[p]++; re = max( re,ccnt[p] ); } LL t = fail[p]; while( t && val[t] ){ ccnt[t]++; re = max( re,ccnt[t] ); t = last[t]; } } } }g; int main() { LL n; char str[200][100]; char str2[1000010]; while( 1 == scanf("%d",&n) && n){ init(); g.init();re = -1; for( LL i = 1;i <= n;i++ ){ scanf("%s",str[i]); g.Insert( str[i],i ); } g.Build(); scanf("%s",str2); g.Find( str2 ); printf("%d\n",re); for( LL i = 1;i <= n;i++ ){ if( ccnt[ma[i]] == re ) printf("%s\n",str[i]); } } return 0; }
