fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int P[1003][10],LCP[1003],Pow[12],SA[1003];
  4.  
  5. struct tuplee
  6. {
  7.  int index,first,second;    
  8. }L[1003];
  9.  
  10. bool comp(tuplee &a,tuplee &b)
  11. {
  12.  if(a.first==b.first)
  13.  return (a.second < b.second);
  14.  else
  15.  return (a.first < b.first);
  16. }
  17.  
  18. int build_suffix(string s)
  19. {
  20.  int n=s.size();    
  21.  int i,j;
  22.  
  23.  for(i=0;i<n;i++)
  24.  P[i][0]=(int)s[i];
  25.  
  26.  for(i=1;Pow[i-1]<n;i++)
  27.  {
  28.    for(j=0;j<n;j++)
  29.    {
  30.      L[j].index=j;
  31.      L[j].first=P[j][i-1];
  32.      L[j].second=((j+Pow[i-1]<n)?P[j+Pow[i-1]][i-1]:-1);
  33.    }
  34.  
  35.    sort(L,L+n,comp);
  36.  
  37.    for(j=0;j<n;j++)
  38.   P[L[j].index][i]=((j>0 && L[j].first==L[j-1].first && L[j].second==L[j-1].second)?P[L[j-1].index][i]:j); 
  39.  
  40.  }
  41.  
  42.  i--;
  43.  
  44.  for(j=0;j<n;j++)
  45.  SA[P[j][i]]=j;
  46.  
  47.  return i;
  48. }
  49.  
  50. int lcp(int x,int y,int step,int n)
  51. { 
  52.   int i;
  53.   int len=0;
  54.   for(i=step;i>=0;i--)
  55.   {
  56.     if(P[x][i]==P[y][i] && x<n && y<n)  
  57.     { 
  58.      len+=Pow[i];
  59.      x=x+Pow[i];
  60.      y=y+Pow[i];
  61.     }  
  62.  
  63.   }
  64.     return len;   
  65. }
  66.  
  67. int solve(int n,int step)
  68. { 
  69.  int i,ans=0;    
  70.  
  71.  for(i=1;i<n;i++)
  72.  ans+=lcp(SA[i],SA[i-1],step,n);
  73.  
  74.  ans=(n*(n+1))/2 -(ans);
  75.  
  76.  return ans;
  77. }
  78.  
  79. int main()
  80. {
  81.   ios_base::sync_with_stdio(0);
  82.   cin.tie(0);
  83.   cout.tie(0);
  84.  
  85.   int t;
  86.   cin>>t;
  87.   int i;
  88.   Pow[0]=1;
  89.   for(i=1;i<=10;i++)
  90.   Pow[i]=2*Pow[i-1];
  91.  
  92.   while(t--)
  93.   { 
  94.     string s;
  95.     cin>>s;
  96.     int n=s.size();
  97.     int step=build_suffix(s);
  98.     cout<<solve(n,step)<<endl;
  99.   }
  100.  
  101.  return 0;    
  102. }
Success #stdin #stdout 0s 4540KB
comments (?)
stdin 
2
CCCCC
ABABA
stdout 
5
9
https://ideone.com/EdtWF3
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!