【后缀数组 不同的字串个数】SPOJ - SUBST1 New Distinct Substrings

Problem Description

给你一个串，问你这个串有多少个不同的字串

思路：

后缀数组学习过程：wwl巨巨讲解了一波，然后参考博客，09年集训队论文后缀数组–处理字符串的有力工具。

后缀串，按字典序从小到大排序。求两两之间的公共字串长度，就是height[]数组。
height[i]：后缀串，按字典序从小到大排序，第 i 后缀串 和 第 i-1 后缀串的最长公共前缀；
知道 height[] 数组后，我们就知道任意两个后缀串的最长公共前缀 = 它们之间 height[] 数组的最小值。例如上图：aaab 和 abaaaab 的最长公共前缀 = 之间的最小值 1。
证明：a 和 b 的 LCP = 3，b 和 c 的 LCP = 4，所以 a 和 c 的 LCP = 3，用到这个理论。
思路：这题是求不同子串的个数，可以转变为两种方式：
1：每个子串一定是某个后缀的前缀，那么原问题等价于求所有后缀不同前缀的个数。
后缀串，按字典序从小到大的顺序，对于每次新加进来第 k 小的后缀串，它将产生 n - sa[k] - 1 个前缀，但是有 height[k] 个是和前面的前缀一样的。所以新加进来的后缀串贡献了：n - sa[k] - 1 + height[k] 个不同的子串。累加后就是原问题答案。
2：每个子串一定是某个后缀的前缀，那么原问题等价于求 总的子串个数 - 所有后缀相同前缀的个数。
总的子串个数：n*(n+1)/2
所有后缀相同前缀的个数：对于新加进来的后缀串，只有 height[i] 个前缀是相同的，所以结果为 height[] 的累加和。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int cntA[maxn], cntB[maxn], sa[maxn], tsa[maxn], A[maxn], B[maxn], height[maxn];
int Rank[maxn];
long long n;//串的长度的平方会超过int
char ch[maxn];
//sa[i]代表第i小的后缀位置，Rank[i]代表第i位置的后缀，排名第几小
void solve()//就是为了求sa[],Rank[],height[]数组。sa[]和Rank[]数组是互逆的，所以知道其中一个另外一个就可以O(n)复杂度求出来
{
    for(int i = 0; i < 256; i++) cntA[i] = 0;
    for(int i = 1; i <= n; i++) cntA[ch[i-1]]++;
    for(int i = 1; i < 256; i++) cntA[i] += cntA[i-1];
    for(int i = n; i; i--) sa[cntA[ch[i-1]]--] = i;
    //上面为了求sa[]数组
    Rank[sa[1]] = 1;
    for(int i = 2; i <= n; i++)
    {
        Rank[sa[i]] = Rank[sa[i-1]];
        if(ch[sa[i]-1] != ch[sa[i-1]-1]) Rank[sa[i]]++;
    }
    //上面的那么多代码，就是为了求后缀长度为1的Rank[]数组
    for(int l = 1; Rank[sa[n]] < n; l <<= 1)//倍增后缀长度求Rank[]数组，长度不够补0
    {
        memset(cntA, 0, sizeof(cntA));
        memset(cntB, 0, sizeof(cntB));
        for(int i = 1; i <= n; i++)
        {
            cntA[A[i] = Rank[i]]++;
            cntB[B[i] = (i+l <= n)?Rank[i+l]:0]++;
        }
        for(int i = 1; i <= n; i++) cntB[i] += cntB[i-1];
        for(int i = n; i; i--) tsa[cntB[B[i]]--] = i;
        for(int i = 1; i <= n; i++) cntA[i] += cntA[i-1];
        for(int i = n; i; i--) sa[cntA[A[tsa[i]]]--] = tsa[i];
        //上面为了求sa[]数组。i是第一类，i+l是第二类，tsa[i]代表第二类第i小的后缀位置
        Rank[sa[1]]=1;
        for(int i = 2; i <= n; i++)
        {
            Rank[sa[i]] = Rank[sa[i-1]];
            if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) Rank[sa[i]]++;
        }
        //求Rank[]数组
    }
    for(int i = 1, j = 0; i <= n; i++)//求height[]数组
    {
        if(j) j--;
        while(ch[i+j-1] == ch[sa[Rank[i]-1] + j - 1]) j++;
        height[Rank[i]] = j;
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", ch);
        n = strlen(ch);
        if(n == 1)
        {
            printf("1\n");
            continue;
        }
        solve();
        long long ans = (n+1)*n/2;
        for(int i = 2; i <= n; i++) ans -= height[i];//减去所有重复的字串
        printf("%lld\n", ans);
    }
}