给一个字符串求有多少个不相同子串。

每一个子串一定都是某一个后缀的前缀。由此可以推断出总共有(1+n)*n/2个子串，那么下面的任务就是找这些子串中重复的子串。

在后缀数组中后缀都是排完序的，从sa[1]到sa[n]，这么思考以某个串为前缀的子串有几个，那么容易想到重复子串的个数其实就是∑height[i]。

所以结果就是(1+n)*n/2-∑height[i]。

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 #define INF (1<<30) 6 #define MAXN 55000 7  8 int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN]; 9 int cmp(int *r,int a,int b,int l){10     return r[a]==r[b] && r[a+l]==r[b+l];11 }12 int sa[MAXN],rank[MAXN],height[MAXN];13 void SA(int *r,int n,int m){14     int *x=wa,*y=wb;15 16     for(int i=0; i
        
         =0; --i) sa[--ws[x[i]]]=i;20 21     int p=1;22     for(int j=1; p
         
          =j) y[p++]=sa[i]-j;26         for(int i=0; i
          
           =0; --i) sa[--ws[wv[i]]]=y[i];31 swap(x,y); x[sa[0]]=0; p=1;32 for(int i=1; i