fork download
copy 
  1. /// sa&lcp by muoii
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define tag "spoj"
  6. #define maxn 0
  7. #define module 0
  8. #define oo 1000000007LL
  9. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  10.  
  11. int n;
  12. string s;
  13. vector<int> sa,rak,tmp,lcp;
  14. int gap;
  15.  
  16. bool sufcmp(const int &x,const int &y){
  17.  
  18.     if (rak[x]!=rak[y]) return rak[x]<rak[y];
  19.     return (x+gap<=n && y+gap<=n) ? rak[x+gap]<rak[y+gap] : x>y;
  20. }
  21.  
  22. void buildSA(){
  23.     sa=rak=tmp=vector<int>(n+1);
  24.  
  25.     for(int i=1;i<=n;i++) sa[i]=i,rak[i]=s[i],tmp[i]=0;
  26.  
  27.     for(gap=1;gap<=n && (gap==1 || rak[sa[n]]<n);gap<<=1)
  28.     {
  29.         sort(sa.begin()+1,sa.begin()+n+1,sufcmp);
  30.  
  31.         for(int i=1;i<=n;i++) tmp[sa[i]] = tmp[sa[i-1]] + sufcmp(sa[i-1],sa[i]);
  32.         for(int i=1;i<=n;i++) rak[i]=tmp[i];
  33.     }
  34.  
  35. }
  36.  
  37. void buildLCP(){
  38.     lcp=vector<int>(n+1);
  39.  
  40.     for(int i=1,k=0;i<=n;i++)
  41.         if(rak[i]>1)
  42.         {
  43.             for(int j=sa[rak[i]-1];s[i+k]==s[j+k];) ++k;
  44.  
  45.             lcp[rak[i]]=k;
  46.  
  47.             k-=(k>0);
  48.         }
  49. }
  50.  
  51. int main()
  52. {
  53.     #ifdef dmdd
  54.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  55.     #endif // dmdd
  56.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  57.  
  58.     cin>>s;n=s.size();s="$"+s;
  59.  
  60.     buildSA();buildLCP();
  61.     for(int i=1;i<=n;i++) cout<<sa[i]<<" : "<<lcp[i]<<"\n";
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jJkr1R
language:
C++14 (gcc 8.3)
created:
6 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!