ulvis.paste.net - pastebin

Paste Search Dynamic
Recent pastes
countDistinctSubstrings
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct suffix{
  5.         int index;
  6.         int rank[2];
  7. };
  8.  
  9. bool cmpFunc( const suffix &a, const suffix &b ){
  10.         if( a.rank[0] == b.rank[0] )
  11.                 return a.rank[1] < b.rank[1];
  12.         return a.rank[0] < b.rank[0];
  13. }
  14.  
  15. vector<int> getSuffixArray(string s){
  16.         int n = s.size();
  17.         vector<suffix> suffixes(n);
  18.        
  19.         for(int i=0;i<n;i++){
  20.                 suffixes[i].index = i;
  21.                 suffixes[i].rank[0] = s[i]-'a';
  22.                 suffixes[i].rank[1] = i == n-1 ? -1 : s[i+1]-'a';
  23.         }
  24.        
  25.         sort(suffixes.begin(),suffixes.end(),cmpFunc);
  26.        
  27.         vector<int> ind(n);
  28.        
  29.         for(int k=4;k<2*n;k*=2){
  30.                
  31.                 int rank = 0;
  32.                 int prev_rank = suffixes[0].rank[0];
  33.                 suffixes[0].rank[0] = 0;
  34.                 ind[suffixes[0].index] = 0;
  35.                
  36.                 for(int i=1;i<n;i++){
  37.                         if( suffixes[i].rank[0] == prev_rank && suffixes[i].rank[1] == suffixes[i-1].rank[1] ){
  38.                                 suffixes[i].rank[0] = rank;
  39.                         }else{
  40.                                 prev_rank = suffixes[i].rank[0];
  41.                                 suffixes[i].rank[0] = ++rank;
  42.                         }
  43.                         ind[suffixes[i].index] = i;
  44.                 }
  45.                
  46.                 for(int i=0;i<n;i++){
  47.                         int nextIndex = suffixes[i].index + k/2;
  48.                         suffixes[i].rank[1] = nextIndex < n ? suffixes[ind[nextIndex]].rank[0] : -1;
  49.                 }
  50.                 sort(suffixes.begin(),suffixes.end(),cmpFunc);
  51.         }
  52.         vector<int> SA;
  53.         for(auto s:suffixes){
  54.                 SA.push_back(s.index);
  55.         }
  56.         return SA;
  57. }
  58.  
  59. vector<int> getLCPArray(string s, vector<int> &SA){
  60.        
  61.         int n = s.size(), k=0;
  62.         vector<int> rank(n);
  63.         vector<int> lcp(n);
  64.        
  65.         for(int i=0;i<n;i++) rank[ SA[i] ] = i;
  66.        
  67.         for(int i=0;i<n;i++,k?k--:0){
  68.                 if( rank[i] == n-1 ){
  69.                         k=0;
  70.                         continue;
  71.                 }
  72.                
  73.                 int j = SA[ rank[i] + 1 ];
  74.                 while( i+k<n && j+k<n && s[i+k] == s[j+k] ) k++;
  75.                 lcp[ rank[i] ]=k;
  76.         }
  77.         return lcp;
  78. }
  79.  
  80. int countDistinctSubstrings(string s){
  81.         int n = s.size();
  82.         vector<int> suffixArray = getSuffixArray(s);
  83.         vector<int> lcp = getLCPArray(s, suffixArray);
  84.         int result = n - suffixArray[0];
  85.         for(int i=1;i<n;i++){
  86.                 result += ( n - suffixArray[i] ) - lcp[i-1];
  87.         }
  88.         return result;
  89. }
  90.  
  91. int main() {
  92.         string s;
  93.         cin>>s;
  94.         cout << countDistinctSubstrings(s) << "\n";
  95.         return 0;
  96. }
Parsed in 0.038 seconds