Advertisement
Guest User

Untitled

a guest
Dec 9th, 2015
421
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.48 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(v) (v).begin(),(v).end()
  4. #define INF int(1e8)
  5. #define NINF int(-1e8)
  6. #define clr(a,v) memset(a,v,sizeof(a))
  7. #define ll long long
  8. #define ull unsigned long long
  9. #define ld long double
  10. #define eps 1e-8
  11. #define PI acos(-1)
  12. #define MOD (ll)(1e9 + 7)
  13. #define readFile freopen("in.txt","r",stdin)
  14. #define fastIO ios::sync_with_stdio(0)
  15.  
  16. using namespace std;
  17.  
  18. const int N = 200010;
  19. int sufArr[N], tmpSufArr[N], rank[N], tmpRank[N], lcp[N];
  20. int len;
  21. char text[N];
  22. char res[301][301];
  23.  
  24. void radixSort(int k){
  25.     int freq[N] = {0}, mx = max(300,len);
  26.     for(int i = 0; i < len; i++) freq[i+k < len ? rank[i+k] : 0]++;
  27.     int acum = 0;
  28.     for(int i = 0; i < mx; i++){
  29.         int sh = freq[i]; freq[i] = acum;
  30.         acum += sh;
  31.     }
  32.     for(int i = 0; i < len; i++) tmpSufArr[freq[sufArr[i]+k < len ? rank[sufArr[i]+k] : 0 ]++] = sufArr[i];
  33.     for(int i = 0; i < len; i++) sufArr[i] = tmpSufArr[i];
  34. }
  35.  
  36. void buildSuffixArray(){
  37.     clr(sufArr,0); clr(tmpSufArr,0); clr(rank,0); clr(tmpRank,0);
  38.     for(int i = 0; i < len; i++) sufArr[i] = i, rank[i] = text[i];
  39.     for(int k = 1; k < len; k <<= 1){
  40.         radixSort(k);
  41.         radixSort(0);
  42.         int r = 0;
  43.         tmpRank[sufArr[0]] = r;
  44.         for(int i = 1; i < len; i++)
  45.             if(rank[sufArr[i]]==rank[sufArr[i-1]] && rank[sufArr[i]+k]==rank[sufArr[i-1]+k])
  46.                 tmpRank[sufArr[i]] = r;
  47.             else tmpRank[sufArr[i]] = ++r;
  48.         for(int i = 0; i < len; i++) rank[i] = tmpRank[i];
  49.         if(rank[sufArr[len-1]] == len-1) break;
  50.     }
  51. }
  52.  
  53. void buildLcp(){
  54.     clr(lcp,0);
  55.     int pos[N] = {0}, plcp[N] = {0}, l = 0;
  56.     pos[sufArr[0]] = -1;
  57.     for(int i = 1; i < len; i++) pos[sufArr[i]] = sufArr[i-1];
  58.     for(int i = 0; i < len; i++){
  59.         if(pos[i]==-1){
  60.             plcp[i] = 0;
  61.             continue;
  62.         }
  63.         while(text[i+l] == text[pos[i]+l]) l++;
  64.         plcp[i] = l;
  65.         l = max(l-1,0);
  66.     }
  67.     for(int i = 0; i < len; i++) lcp[i] = plcp[sufArr[i]];
  68. }
  69.  
  70. int main(){
  71.  
  72. #ifndef ONLINE_JUDGE
  73.     readFile;
  74. #endif
  75.  
  76.     char t1[N],t2[N]; int tc = 0;
  77.     while(scanf("%s",t1) != EOF){
  78.         if(tc++) printf("\n");
  79.         scanf("%s\n",t2);
  80.  
  81.         int l1 = strlen(t1), l2 = strlen(t2);
  82.  
  83.         for(int i = 0; i < l1; i++) text[i] = t1[i];
  84.         text[l1++] = '#';
  85.         for(int i = 0; i < l2; i++) text[i+l1] = t2[i];
  86.         len = strlen(text);
  87.         text[len++] = '$';
  88.  
  89.         buildSuffixArray();
  90.         buildLcp();
  91.  
  92.         int lcs = 0;
  93.         for(int i = 1; i < len; i++){
  94.             int ow1 = sufArr[i-1], ow2 = sufArr[i];
  95.             if(ow1>ow2) swap(ow1,ow2);
  96.             if(ow1<l1&&ow2>=l1&&lcp[i]<=(l1-ow1)) lcs = max(lcs,lcp[i]);
  97.         }
  98.         if(!lcs){
  99.             printf("No common sequence.\n\n");
  100.             continue;
  101.         }
  102.         int idx = 0;
  103.         for(int i = 1; i < len; i++){
  104.             if(lcp[i] == lcs){
  105.                 int ow1 = sufArr[i-1], ow2 = sufArr[i];
  106.                 if(ow1>ow2) swap(ow1,ow2);
  107.                 if(ow1<l1&&ow2>=l1&&lcp[i]<=(l1-ow1)){
  108.                     int kk = 0;
  109.                     for(int j = sufArr[i]; j < sufArr[i]+lcs; j++) res[idx][kk++] = text[j];
  110.                     res[idx][kk] = '\0';
  111.                     idx++;
  112.                 }
  113.             }
  114.         }
  115.         printf("%s\n",res[0]);
  116.         for(int i = 1; i < idx; i++){
  117.             if(strcmp(res[i],res[i-1])) printf("%s\n",res[i]);
  118.         }
  119.     }
  120.     return 0;
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement