Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define filer() freopen("in.txt","r",stdin)
- #define filew() freopen("out.txt","w",stdout)
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- #include<math.h>
- #include<algorithm>
- #include<queue>
- #include<stack>
- #include<string>
- #include<vector>
- #include <map>
- #define INF 1<<29
- #define PI pair<int,int>
- #define f first
- #define s second
- #define SET(a, x) memset((a), (x), sizeof(a))
- #define pb push_back
- #define i64 long long
- #define EPS (1e-9)
- using namespace std;
- typedef vector<int> VI;
- typedef vector<PI> vii;
- //i64 INF=(i64)((i64)1<<(i64)59);
- int N;
- const bool sfx_rotate = false;
- const int maxlen = 1000003;
- const int maxh = 21;
- const int alphabet = 256;
- int n;
- //initialize n;
- char s[maxlen];
- int cnt[maxlen], p[maxlen], c[maxh][maxlen], pn[maxlen], *cn, h;
- int lcp (int i, int j) {
- int ans = 0;
- for (int k=h; k>=0; --k) if (c[k][i] == c[k][j]) ans += 1<<k, i += 1<<k, j += 1<<k;
- return ans;
- }
- void build_sfx_array() {
- if (!sfx_rotate) ++n;
- memset(cnt,0,alphabet*sizeof(cnt[0]));
- for (int i=0; i<n; ++i) ++cnt[(int)s[i]];
- for (int i=1; i<alphabet; ++i) cnt[i] += cnt[i-1];
- for (int i=0; i<n; ++i) p[--cnt[(int)s[i]]] = i;
- c[0][p[0]] = 0;
- int classes = 1;
- for (int i=1; i<n; ++i) classes += (s[p[i]] != s[p[i-1]]), c[0][p[i]] = classes-1;
- cn = c[1];
- for (h=0; (1<<h)<n && (1<<h)<=128; ++h) {
- for (int i=0; i<n; ++i) pn[i] = p[i] - (1<<h), pn[i] += pn[i]<0?n:0;
- memset(cnt,0,classes*sizeof(cnt[0]));
- for (int i=0; i<n; ++i) ++cnt[c[h][pn[i]]];
- for (int i=1; i<classes; ++i) cnt[i] += cnt[i-1];
- for (int i=n-1; i>=0; --i) p[--cnt[c[h][pn[i]]]] = pn[i];
- cn[p[0]] = 0;
- classes = 1;
- for (int i=1; i<n; ++i) {
- int mid1 = (p[i] + (1<<h)) % n, mid2 = (p[i-1] + (1<<h)) % n;
- if (c[h][p[i]] != c[h][p[i-1]] or c[h][mid1] != c[h][mid2]) ++classes;
- cn[p[i]] = classes-1;
- }
- cn = c[h+2];
- }
- if (!sfx_rotate) {
- --n;
- for (int i=0; i<n; ++i) p[c[h][i]-1] = i;
- } else {
- memset(cnt,0,classes*sizeof(cnt[0]));
- for (int i=0; i<n; ++i) ++cnt[c[h][i]];
- for (int i=1; i<classes; ++i) cnt[i] += cnt[i-1];
- for (int i=n-1; i>=0; --i) p[--cnt[c[h][i]]] = i;
- }
- }
- char pat[155][75];
- int vst[155];
- int find(int mid,int i)
- {
- int j=p[mid],k;
- int sz=strlen(pat[i]);
- for( k=0;j<N && k<sz;k++,j++)
- {
- if(s[j]<pat[i][k])return -1;
- else if(s[j]>pat[i][k])return 1;
- }
- if(sz==k)return 0;
- return -1;
- }
- int search1(int lo,int hi,int i)
- {
- int mid,ans=-1,ind;
- while(lo<=hi)
- {
- mid=(lo+hi)/2;
- ind=find(mid,i);
- if(ind==0)
- {
- ans=mid;
- hi=mid-1;
- }
- else if(ind==-1)lo=mid+1;
- else hi=mid-1;
- }
- return ans;
- }
- int search2(int lo,int hi,int i)
- {
- int mid,ans=-1,ind;
- while(lo<=hi)
- {
- mid=(lo+hi)/2;
- ind=find(mid,i);
- if(ind==0)
- {
- ans=mid;
- //hi=mid-1;
- lo=mid+1;
- }
- else if(ind==-1)lo=mid+1;
- else hi=mid-1;
- }
- return ans;
- }
- int main()
- {
- //filer();
- int T,cas=0;
- int i,j;
- while(scanf("%d",&T)==1)
- {
- if(T==0)break;
- for(i=0;i<T;i++)scanf("%s",pat[i]);
- SET(vst,0);
- scanf("%s",s);
- N=strlen(s);
- n=N;
- build_sfx_array();
- //for(i=0;i<strlen(s);i++)cout<<c[i]<<' ';cout<<endl;
- //for(i=0;i<strlen(s);i++)cout<<p[i]<<' ';cout<<endl;
- int mx=-1;
- //int ind=-1;
- int ind1,ind2;
- for(i=0;i<T;i++)
- {
- ind1=search1(0,N-1,i);
- if(ind1!=-1)ind2=search2(ind1,N-1,i);
- if(ind1!=-1)vst[i]=ind2-ind1+1;
- mx=max(vst[i],mx);
- }
- //for(i=0;i<T;i++)cout<<vst[i]<<' ';cout<<endl;
- printf("%d\n",mx);
- int cnt=0;
- //if(mx>0)
- for(i=0;i<T;i++)
- {
- //cnt++;
- if(vst[i]==mx)printf("%s\n",pat[i]);
- }
- /*
- if(cnt>1)
- {
- for(i=0;i<T;i++)
- {
- //cnt++;
- if(vst[i]==mx)printf("%s\n",pat[i]);
- }
- //printf("")
- }*/
- }
- return 0;
- }
- /*
- Test Case:
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement