fork(1) download 
  1. // author : prem ktiw
  2. // count no. of different substrings
  3.  
  4. # include<iostream>
  5. # include<cstdlib>
  6. # include<cstring>
  7. # include<cstdio>
  8.  
  9.  typedef long long int lli;
  10.  
  11.  
  12.  using namespace std;
  13.  
  14.  namespace SuffixArray{
  15.  
  16. # define MAX_N 3001
  17. char STR[MAX_N];
  18. int n;
  19. int RA[MAX_N], tRA[MAX_N];
  20. int SA[MAX_N], tSA[MAX_N];
  21. int LCP[MAX_N];
  22. int c[MAX_N];
  23.  
  24. void countSort(int k) {
  25.   int i, sum, maxi = max(300, n);
  26.   memset(c, 0, sizeof c);
  27.   for (i = 0; i < n; i++)
  28.     c[i + k < n ? RA[i + k] : 0]++;
  29.   for (i = sum = 0; i < maxi; i++) {
  30.     int t = c[i]; c[i] = sum; sum += t;
  31.   }
  32.   for (i = 0; i < n; i++)
  33.     tSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i];
  34.   for (i = 0; i < n; i++)
  35.     SA[i] = tSA[i];
  36. }
  37.  
  38. void buildSA() {
  39.   int i, k, r;
  40.   for (i = 0; i < n; i++) RA[i] = STR[i];
  41.   for (i = 0; i < n; i++) SA[i] = i;
  42.   for (k = 1; k < n; k <<= 1) {
  43.     countSort(k);
  44.     countSort(0);
  45.     tRA[SA[0]] = r = 0;
  46.     for (i = 1; i < n; i++)
  47.       tRA[SA[i]] =
  48.       (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;
  49.     for (i = 0; i < n; i++)
  50.       RA[i] = tRA[i];
  51.     if (RA[SA[n-1]] == n-1) break;
  52.   }
  53. }
  54.  
  55.  
  56. void buildLCP(){
  57. 	//for all suffixes starting from location i onwards
  58. 	for(int i=0,k=0;i<n;++i,k?--k:0){
  59. 		if(RA[i]==n-1){k==0;continue;} //this is last suffix in SA
  60. 		int j=SA[RA[i]+1];
  61. 		while(i+k < n && j+k < n && STR[i+k] == STR[j+k])++k;
  62. 		LCP[RA[i]] = k;
  63. 	}
  64. }
  65.  
  66. // namespace ends
  67. }
  68.  
  69. using namespace SuffixArray;
  70.  
  71.  lli how_many(int n){
  72.  
  73.     int x = n - SA[0];
  74.     lli ans = x ;
  75.  
  76.  
  77.     for(int i = 0 ; i < n-1; ++i){
  78.         x = n - (SA[i+1] + LCP[i]);
  79.         ans += x;
  80.     }
  81.  
  82.     return ans;
  83.  }
  84.  
  85. int **allot(int n,int m){
  86. int **st = new int*[n+1];
  87. for(int i=0;i<=n;st[i] = new int[m+1](),++i);
  88. return st; }
  89.  
  90.  int main(){
  91.     int n,q;
  92.     cin>>n>>q;
  93.  
  94.     char *str = new char[n+1]();
  95.  
  96.     int **mat = allot(3000,3000);
  97.  
  98.  
  99.     cin>>str;
  100.  
  101.     int a,b;
  102.  
  103.     while(q--){
  104.         cin>>a>>b;
  105.  
  106.         if(a == b){cout << 1 <<endl;continue;}
  107.         if(mat[a][b]){cout<<mat[a][b]<<endl;continue;}
  108.  
  109.         char ch = str[b+1];
  110.         str[b+1] = 0;
  111.         strcpy(STR,str+a);
  112.         str[b+1] = ch;
  113.  
  114.         SuffixArray :: n = b-a+1;
  115.  
  116.         buildSA();
  117.         buildLCP();
  118.  
  119.  
  120.         cout<<(mat[a][b] = how_many(b-a+1))<<endl;
  121.     }
  122.  
  123.  
  124.  
  125.  return 0;
  126.  }
  127.  
Success #stdin #stdout 0.03s 38740KB
comments (?)
stdin 
adsdb
stdout 
Standard output is empty
https://ideone.com/QLelXQ
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 days 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!