题目描述】

给定一个字符串，计算其不同的子串个数。

【输入格式】

一行一个仅包含大写字母的字符串，长度<=50000

【输出格式】

一行一个正整数，即不同的子串个数。

【样例输入】

ABABA

【样例输出】

9

 

题解：

显然后缀可以是一个子串，然后后缀中可能包含多个子串。

我们考虑不重复统计，容易发现 一个后缀的贡献为L-high[i]+1

因为high[i]之前的显然可以在后面的串中被统计到，所以可以避免重复

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 using namespace std; 8 const int N=50005; 9 char s[N];int n,k,rk[N],sa[N],tmp[N],high[N];10 bool comp(int i,int j){11 if(rk[i]!=rk[j])return rk[i]