Advertisement
Guest User

Untitled

a guest
Dec 14th, 2015
427
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.25 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. int const N = 100010;
  19. int sufArr[N], tmpSufArr[N], rank[N], tmpRank[N], lcp[N], n;
  20. char text[N];
  21.  
  22. void radixSort(int k){
  23.     int freq[N] = {0}, acum = 0, mx = max(300,n);
  24.     for(int i = 0; i < n; i++) freq[i+k < n ? rank[i+k] : 0]++;
  25.     for(int i = 0; i < mx; i++){
  26.         int t = freq[i]; freq[i] = acum;
  27.         acum += t;
  28.     }
  29.     for(int i = 0; i < n; i++) tmpSufArr[freq[sufArr[i]+k < n ? rank[sufArr[i]+k] : 0]++] = sufArr[i];
  30.     for(int i = 0; i < n; i++) sufArr[i] = tmpSufArr[i];
  31. }
  32.  
  33. void buildSuffixArray(){
  34.     clr(sufArr,0); clr(tmpSufArr,0); clr(rank,0), clr(tmpRank,0);
  35.     for(int i = 0; i < n; i++) sufArr[i] = i, rank[i] = text[i];
  36.     for(int k = 1; k <= n; k <<= 1){
  37.         radixSort(k);
  38.         radixSort(0);
  39.         int r = 0;
  40.         tmpRank[sufArr[0]] = 0;
  41.         for(int i = 1; i < n; i++){
  42.             if(rank[sufArr[i]] == rank[sufArr[i-1]] && rank[sufArr[i]+k] == rank[sufArr[i-1]+k])
  43.                 tmpRank[sufArr[i]] = r;
  44.             else tmpRank[sufArr[i]] = ++r;
  45.         }
  46.         for(int i = 0; i < n; i++) rank[i] = tmpRank[i];
  47.         if(rank[sufArr[n-1]] == n-1) break;
  48.     }
  49. }
  50.  
  51. void buildLcp(){
  52.     clr(lcp,0);
  53.     int pos[N] = {0}, plcp[N]= {0}, l = 0;
  54.     pos[sufArr[0]] = -1;
  55.     for(int i = 1; i < n; i++) pos[sufArr[i]] = sufArr[i-1];
  56.     for(int i = 0; i < n; i++){
  57.         if(pos[i]==-1){
  58.             plcp[i] = 0;
  59.             continue;
  60.         }
  61.         while(text[i+l] == text[pos[i]+l] && i+l < n) l++;
  62.         plcp[i] = l;
  63.         l = max(l-1,0);
  64.     }
  65.     for(int i = 0; i < n; i++) lcp[i] = plcp[sufArr[i]];
  66. }
  67.  
  68. pair<int,int> match(int idx, int len){
  69.     int l = 0, r = n-1;
  70.     pair<int,int> res;
  71.     while(l < r){
  72.         int mid = (l+r)>>1;
  73.         int ans = strncmp(text+sufArr[mid],text+sufArr[idx],len);
  74.         if(ans >= 0) r = mid;
  75.         else l = mid+1;
  76.     }
  77.     res.first = l;
  78.     l = 0; r = n-1;
  79.     while(l < r){
  80.         int mid = (l+r)>>1;
  81.         int ans = strncmp(text+sufArr[mid],text+sufArr[idx],len);
  82.         if(ans > 0) r = mid;
  83.         else l = mid+1;
  84.     }
  85.     if(strncmp(text+sufArr[r],text+sufArr[idx],len)) r--;
  86.     res.second = r;
  87.     return res;
  88. }
  89.  
  90. int main(){
  91.  
  92. #ifndef ONLINE_JUDGE
  93.     readFile;
  94. #endif
  95.    
  96.     int t; scanf("%d",&t);
  97.     while(t--){
  98.         scanf("%s",text);
  99. //        strcat(text,"$");
  100.         n = strlen(text);
  101.        
  102.         buildSuffixArray();
  103.         buildLcp();
  104.        
  105.         int mx = 0, idx = -1;
  106.         for(int i = 1; i < n; i++){
  107.             if(lcp[i] > mx) mx = lcp[i], idx = i;
  108.         }
  109.        
  110.         if(!mx){
  111.             printf("No repetitions found!\n");
  112.             continue;
  113.         }
  114.        
  115.         pair<int,int> oc = match(idx-1,mx);
  116.         for(int i = sufArr[idx]; i < sufArr[idx]+mx; i++) printf("%c",text[i]);
  117.         printf(" %d\n",oc.second-oc.first+1);
  118.     }
  119.    
  120.     return 0;
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement