fork download
copy 
  1. #include "stdio.h"
  2. #include "stdlib.h"
  3. #include "string.h"
  4. #include "algorithm"
  5. using namespace std;
  6.  
  7. // Begins Suffix Arrays implementation
  8. // O(n log n) - Manber and Myers algorithm
  9. // Refer to "Suffix arrays: A new method for on-line txting searches",
  10. // by Udi Manber and Gene Myers
  11.  
  12. //Usage:
  13. // Fill txt with the characters of the txting.
  14. // Call SuffixSort(n), where n is the length of the txting stored in txt.
  15. // That's it!
  16.  
  17. //Output:
  18. // SA = The suffix array. Contains the n suffixes of txt sorted in lexicographical order.
  19. //       Each suffix is represented as a single integer (the SAition of txt where it starts).
  20. // iSA = The inverse of the suffix array. iSA[i] = the index of the suffix txt[i..n)
  21. //        in the SA array. (In other words, SA[i] = k <==> iSA[k] = i)
  22. //        With this array, you can compare two suffixes in O(1): Suffix txt[i..n) is smaller
  23. //        than txt[j..n) if and only if iSA[i] < iSA[j]
  24. const int MAX = 100010;
  25. char txt[MAX]; //input
  26. int iSA[MAX], SA[MAX]; //output
  27. int cnt[MAX], next[MAX]; //internal
  28. bool bh[MAX], b2h[MAX];
  29.  
  30. // Compares two suffixes according to their first characters
  31. bool smaller_first_char(int a, int b){
  32.   return txt[a] < txt[b];
  33. }
  34.  
  35. void suffixSort(int n){
  36.   //sort suffixes according to their first characters
  37.   for (int i=0; i<n; ++i){
  38.     SA[i] = i;
  39.   }
  40.   sort(SA, SA + n, smaller_first_char);
  41.   //{SA contains the list of suffixes sorted by their first character}
  42.  
  43.   for (int i=0; i<n; ++i){
  44.     bh[i] = i == 0 || txt[SA[i]] != txt[SA[i-1]];
  45.     b2h[i] = false;
  46.   }
  47.  
  48.   for (int h = 1; h < n; h <<= 1){
  49.     //{bh[i] == false if the first h characters of SA[i-1] == the first h characters of SA[i]}
  50.     int buckets = 0;
  51.     for (int i=0, j; i < n; i = j){
  52.       j = i + 1;
  53.       while (j < n && !bh[j]) j++;
  54.       next[i] = j;
  55.       buckets++;
  56.     }
  57.     if (buckets == n) break; // We are done! Lucky bastards!
  58.     //{suffixes are separted in buckets containing txtings starting with the same h characters}
  59.  
  60.     for (int i = 0; i < n; i = next[i]){
  61.       cnt[i] = 0;
  62.       for (int j = i; j < next[i]; ++j){
  63.         iSA[SA[j]] = i;
  64.       }
  65.     }
  66.  
  67.     cnt[iSA[n - h]]++;
  68.     b2h[iSA[n - h]] = true;
  69.     for (int i = 0; i < n; i = next[i]){
  70.       for (int j = i; j < next[i]; ++j){
  71.         int s = SA[j] - h;
  72.         if (s >= 0){
  73.           int head = iSA[s];
  74.           iSA[s] = head + cnt[head]++;
  75.           b2h[iSA[s]] = true;
  76.         }
  77.       }
  78.       for (int j = i; j < next[i]; ++j){
  79.         int s = SA[j] - h;
  80.         if (s >= 0 && b2h[iSA[s]]){
  81.           for (int k = iSA[s]+1; !bh[k] && b2h[k]; k++) b2h[k] = false;
  82.         }
  83.       }
  84.     }
  85.     for (int i=0; i<n; ++i){
  86.       SA[iSA[i]] = i;
  87.       bh[i] |= b2h[i];
  88.     }
  89.   }
  90.   for (int i=0; i<n; ++i){
  91.     iSA[SA[i]] = i;
  92.   }
  93. }
  94. // End of suffix array algorithm
  95.  
  96.  
  97. // Begin of the O(n) longest common prefix algorithm
  98. // Refer to "Linear-Time Longest-Common-Prefix Computation in Suffix
  99. // Arrays and Its Applications" by Toru Kasai, Gunho Lee, Hiroki
  100. // Arimura, Setsuo Arikawa, and Kunsoo Park.
  101. int lcp[MAX];
  102. // lcp[i] = length of the longest common prefix of suffix SA[i] and suffix SA[i-1]
  103. // lcp[0] = 0
  104. void getlcp(int n)
  105. {
  106.   for (int i=0; i<n; ++i) 
  107.     iSA[SA[i]] = i;
  108.  
  109.   lcp[0] = 0;
  110.  
  111.   for (int i=0, h=0; i<n; ++i)
  112.   {
  113.     if (iSA[i] > 0)
  114.     {
  115.       int j = SA[iSA[i]-1];
  116.       while (i + h < n && j + h < n && txt[i+h] == txt[j+h]) 
  117.           h++;
  118.       lcp[iSA[i]] = h;
  119.  
  120.       if (h > 0) 
  121.         h--;
  122.     }
  123.   }
  124. }
  125. // End of longest common prefixes algorithm
  126. int main()
  127. {
  128.   int len;
  129.  gets(txt);
  130.  len = strlen(txt);
  131.  
  132.  suffixSort(len);
  133.  for (int i = 0; i < len; ++i)
  134.  {
  135.    printf("%d\n",SA[i] );
  136.  }
  137.    return 0;
  138.  }
Success #stdin #stdout 0s 4932KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fjbYBr
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!