1 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int N=155; char str[N][80], T[1110000]; int ch[N*70][26], id, ed[N*70], pre[N*70], num[N]; void ins(char *s, int x) { int p=0; for(int i=0;s[i];i++) { int j=s[i]-'a'; if(ch[p][j]==0) ch[p][j]=++id; p=ch[p][j]; } ed[p]=x; } void build() { queue<int> Q; for(int i=0;i<26;i++)if(ch[0][i])Q.push(ch[0][i]); while(!Q.empty()) { int x=Q.front();Q.pop(); for(int i=0;i<26;i++) { int &y=ch[x][i]; if(y==0) y=ch[pre[x]][i]; else pre[y]=ch[pre[x]][i], Q.push(y); } } } void query(char *s) { int p=0; for(int i=0;s[i];i++) { p=ch[p][s[i]-'a']; for(int j=p;j;j=pre[j]) num[ed[j]]++; } } int main() { int n; while(scanf("%d", &n)!=EOF && n) { id=0;memset(ch,0,sizeof(ch));memset(ed,0,sizeof(ed)); for(int i=1;i<=n; i++)scanf("%s", str[i]), ins(str[i],i); memset(pre,0,sizeof(pre));build(); scanf("%s", T); memset(num,0,sizeof num); query(T); int mx=0;for(int i=1;i<=n;i++) mx=max(mx,num[i]); printf("%d\n", mx); for(int i=1;i<=n;i++) if(num[i]==mx) printf("%s\n", str[i]); } return 0; }
- 1
信息
- ID
- 512
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 8
- 标签
- 递交数
- 187
- 已通过
- 34
- 上传者