Advertisement
farsid

Untitled

Mar 18th, 2013
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.40 KB | None | 0 0
  1. #define filer() freopen("in.txt","r",stdin)
  2. #define filew() freopen("out.txt","w",stdout)
  3. #include<iostream>
  4. #include<stdio.h>
  5. #include<string.h>
  6. #include<math.h>
  7. #include<algorithm>
  8. #include<queue>
  9. #include<stack>
  10. #include<string>
  11. #include<vector>
  12. #include <map>
  13. #define INF 1<<29
  14. #define PI pair<int,int>
  15. #define f first
  16. #define s second
  17. #define SET(a, x) memset((a), (x), sizeof(a))
  18. #define pb push_back
  19. #define i64 long long
  20. #define EPS (1e-9)
  21. using namespace std;
  22. typedef vector<int> VI;
  23. typedef vector<PI> vii;
  24. //i64 INF=(i64)((i64)1<<(i64)59);
  25.  
  26. int N;
  27.  
  28. const bool sfx_rotate = false;
  29. const int maxlen = 1000003;
  30. const int maxh = 21;
  31. const int alphabet = 256;
  32. int n;
  33. //initialize n;
  34. char s[maxlen];
  35. int cnt[maxlen], p[maxlen], c[maxh][maxlen], pn[maxlen], *cn, h;
  36.  
  37. int lcp (int i, int j) {
  38. int ans = 0;
  39. for (int k=h; k>=0; --k) if (c[k][i] == c[k][j]) ans += 1<<k, i += 1<<k, j += 1<<k;
  40. return ans;
  41. }
  42.  
  43. void build_sfx_array() {
  44. if (!sfx_rotate) ++n;
  45. memset(cnt,0,alphabet*sizeof(cnt[0]));
  46. for (int i=0; i<n; ++i) ++cnt[(int)s[i]];
  47. for (int i=1; i<alphabet; ++i) cnt[i] += cnt[i-1];
  48. for (int i=0; i<n; ++i) p[--cnt[(int)s[i]]] = i;
  49. c[0][p[0]] = 0;
  50. int classes = 1;
  51. for (int i=1; i<n; ++i) classes += (s[p[i]] != s[p[i-1]]), c[0][p[i]] = classes-1;
  52. cn = c[1];
  53. for (h=0; (1<<h)<n && (1<<h)<=128; ++h) {
  54. for (int i=0; i<n; ++i) pn[i] = p[i] - (1<<h), pn[i] += pn[i]<0?n:0;
  55. memset(cnt,0,classes*sizeof(cnt[0]));
  56. for (int i=0; i<n; ++i) ++cnt[c[h][pn[i]]];
  57. for (int i=1; i<classes; ++i) cnt[i] += cnt[i-1];
  58. for (int i=n-1; i>=0; --i) p[--cnt[c[h][pn[i]]]] = pn[i];
  59. cn[p[0]] = 0;
  60. classes = 1;
  61. for (int i=1; i<n; ++i) {
  62. int mid1 = (p[i] + (1<<h)) % n, mid2 = (p[i-1] + (1<<h)) % n;
  63. if (c[h][p[i]] != c[h][p[i-1]] or c[h][mid1] != c[h][mid2]) ++classes;
  64. cn[p[i]] = classes-1;
  65. }
  66. cn = c[h+2];
  67. }
  68. if (!sfx_rotate) {
  69. --n;
  70. for (int i=0; i<n; ++i) p[c[h][i]-1] = i;
  71. } else {
  72. memset(cnt,0,classes*sizeof(cnt[0]));
  73. for (int i=0; i<n; ++i) ++cnt[c[h][i]];
  74. for (int i=1; i<classes; ++i) cnt[i] += cnt[i-1];
  75. for (int i=n-1; i>=0; --i) p[--cnt[c[h][i]]] = i;
  76. }
  77. }
  78. char pat[155][75];
  79. int vst[155];
  80.  
  81. int find(int mid,int i)
  82. {
  83. int j=p[mid],k;
  84. int sz=strlen(pat[i]);
  85. for( k=0;j<N && k<sz;k++,j++)
  86. {
  87. if(s[j]<pat[i][k])return -1;
  88. else if(s[j]>pat[i][k])return 1;
  89. }
  90. if(sz==k)return 0;
  91. return -1;
  92. }
  93.  
  94. int search1(int lo,int hi,int i)
  95. {
  96. int mid,ans=-1,ind;
  97.  
  98. while(lo<=hi)
  99. {
  100. mid=(lo+hi)/2;
  101. ind=find(mid,i);
  102.  
  103. if(ind==0)
  104. {
  105. ans=mid;
  106. hi=mid-1;
  107. }
  108. else if(ind==-1)lo=mid+1;
  109. else hi=mid-1;
  110. }
  111. return ans;
  112. }
  113.  
  114. int search2(int lo,int hi,int i)
  115. {
  116. int mid,ans=-1,ind;
  117.  
  118. while(lo<=hi)
  119. {
  120. mid=(lo+hi)/2;
  121. ind=find(mid,i);
  122.  
  123. if(ind==0)
  124. {
  125. ans=mid;
  126. //hi=mid-1;
  127. lo=mid+1;
  128. }
  129. else if(ind==-1)lo=mid+1;
  130. else hi=mid-1;
  131. }
  132. return ans;
  133. }
  134.  
  135. int main()
  136. {
  137. //filer();
  138. int T,cas=0;
  139. int i,j;
  140. while(scanf("%d",&T)==1)
  141. {
  142. if(T==0)break;
  143. for(i=0;i<T;i++)scanf("%s",pat[i]);
  144. SET(vst,0);
  145. scanf("%s",s);
  146. N=strlen(s);
  147. n=N;
  148. build_sfx_array();
  149. //for(i=0;i<strlen(s);i++)cout<<c[i]<<' ';cout<<endl;
  150. //for(i=0;i<strlen(s);i++)cout<<p[i]<<' ';cout<<endl;
  151. int mx=-1;
  152. //int ind=-1;
  153. int ind1,ind2;
  154. for(i=0;i<T;i++)
  155. {
  156. ind1=search1(0,N-1,i);
  157. if(ind1!=-1)ind2=search2(ind1,N-1,i);
  158. if(ind1!=-1)vst[i]=ind2-ind1+1;
  159. mx=max(vst[i],mx);
  160. }
  161. //for(i=0;i<T;i++)cout<<vst[i]<<' ';cout<<endl;
  162. printf("%d\n",mx);
  163. int cnt=0;
  164. //if(mx>0)
  165.  
  166. for(i=0;i<T;i++)
  167. {
  168. //cnt++;
  169. if(vst[i]==mx)printf("%s\n",pat[i]);
  170. }
  171.  
  172.  
  173. /*
  174. if(cnt>1)
  175. {
  176. for(i=0;i<T;i++)
  177. {
  178. //cnt++;
  179. if(vst[i]==mx)printf("%s\n",pat[i]);
  180. }
  181. //printf("")
  182. }*/
  183. }
  184. return 0;
  185. }
  186. /*
  187. Test Case:
  188.  
  189. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement