题目大意

求一个字符串的所有不同字串的个数。

解题思路

一开始看着题,随意瞎蒙了一下height数组的性质,输出 sigma(i-height(i)),1<=i<=n;没想到就直接A了。。。
冷静下来,我来证证:对于字符串s,s的每一个字串一定是s的某个后缀的前缀
那么对于每一个后缀suffix(i),它对答案的贡献为length(suffix(i))-其中与其他字串的重复的个数。
然后只需考虑suffix(i)的字串与其他字串的重复的个数即可
对于suffix(i),与其最相似的后缀为suffix(i-1)或suffix(i+1),因需不重不漏地计算,故统一取suffix(i-1)。
它们重复字串的个数即为其LCP,故为height(i);因此sigma(i-height(i)),1<=i<=n 即为解。

代码

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int T, n;
long long sum;
char s[50005];
int sa[50005], rank[50005], height[50005];
int wa[50005], wb[50005], c[2000];

void Build_sa(int m)
{
    int i, *x=wa, *y=wb;
    for(i=0; i<m; i++) c[i] = 0;
    for(i=0; i<n; i++) c[x[i]=s[i]]++;
    for(i=1; i<m; i++) c[i] += c[i-1];
    for(i=n-1; i>=0; i--) sa[--c[x[i]]] = i;
    for(int k=1; k<=n; k<<=1)
    {
        int p=0;
        for(i=n-1; i>=n-k; i--) y[p++] = i;
        for(i=0; i<n; i++) if(sa[i]>=k) y[p++] = sa[i]-k;
        for(i=0; i<m; i++) c[i] = 0;
        for(i=0; i<n; i++) c[x[y[i]]]++;
        for(i=1; i<m; i++) c[i] += c[i-1];
        for(i=n-1; i>=0; i--) sa[--c[x[y[i]]]] = y[i];
        swap(x,y);
        p=1; x[sa[0]] = 0;
        for(i=1; i<n; i++)
            x[sa[i]] = ((y[sa[i-1]]==y[sa[i]]) && (y[sa[i-1]+k]==y[sa[i]+k]))?p-1:p++;
        if(p>=n) break;
        m = p;
    }
}

void Build_height()
{
    int i, j, k=0;
    for(i=0; i<n; i++) rank[sa[i]] = i;
    for(i=0; i<n; i++)
    if(rank[i])
    {
        if(k) k--;
        j = sa[rank[i]-1];
        while(s[i+k]==s[j+k]) k++;
        height[rank[i]] = k;
    }
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", s);
        n = strlen(s);
        Build_sa(1500);
        Build_height();
        sum = 0;
        for(long long i=1; i<=n; i++) sum += i;
        for(long long i=1; i<n; i++) sum -= height[i];
        printf("%lld\n", sum);
    }
    return 0;
}