[SPOJ 705] New Distinct Substrings

题目链接，求长度为 n 的字符串中不同子串个数

maya，一不小心就看到题解了， ppfish大爷的题解：

按照 sa[i] 的顺序考虑，加入一个新的 sa[i] ，会产生新的 n−sa[i]+1 个子串

而这些子串中与前面所有子串中重复的个数为 height[i]

因此每一个新的后缀对答案的贡献为 n−sa[i]+1−height[i]

真是很有意思的题目啊~！

// SPOJ 1705

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <iostream>
#include <algorithm>

template<class Num>void read(Num &x)
{
    char c; int flag = ;
    while((c = getchar()) < '0' || c > '9')
        if(c == '-') flag *= -;
    x = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        x = (x<<) + (x<<) + (c-'0');
    x *= flag;
    return;
}
template<class Num>void write(Num x)
{
    if(x < ) putchar('-'), x = -x;
    static char s[];int sl = ;
    while(x) s[sl++] = x% + '0',x /= ;
    if(!sl) {putchar('0');return;}
    while(sl) putchar(s[--sl]);
}

const int maxn = ;
char s[maxn];
int n, sa[maxn], rank[maxn];
int c[maxn], height[maxn];
long long ans;

void build_sa(int m)
{
    static int t0[maxn], t1[maxn];
    int *x = t0, *y = t1;

    for(int i = ; i <= m; i++) c[i] = ;
    for(int i = ; i <= n; i++) c[x[i] = s[i]]++;
    for(int i = ; i <= m; i++) c[i] += c[i - ];
    for(int i = n; i >= ; i--) sa[c[x[i]]--] = i;

    for(int k = ; k <= n; k <<= )
    {
        int p = ;
        for(int i = ; i < k; i++) y[++p] = n - i;
        for(int i = ; i <= n; i++)
            if(sa[i] > k) y[++p] = sa[i] - k;
        for(int i = ; i <= m; i++) c[i] = ;
        for(int i = ; i <= n; i++) c[x[y[i]]]++;
        for(int i = ; i <= m; i++) c[i] += c[i - ];
        for(int i = n; i >= ; i--) sa[c[x[y[i]]]--] = y[i];
        std::swap(x, y), x[sa[p = ]] = ;
        for(int i = ; i <= n; i++)
            x[sa[i]] = y[sa[i]] == y[sa[i - ]] && sa[i] + k <= n && sa[i - ] + k <= n && y[sa[i] + k] == y[sa[i - ] + k] ? p : ++p;
        if(p == n) break;
        m = p;  
    }
}
void build_height()
{
    int k = ;
    for(int i = ; i <= n; i++) rank[sa[i]] = i;
    for(int i = ; i <= n; i++)
    {
        if(k != ) k--;
        if(rank[i] == ) continue;
        int j = sa[rank[i] - ];
        while(s[i + k] == s[j + k]) k++;
        height[rank[i]] = k;
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("subst1.in","r",stdin);
    freopen("subst1.out","w",stdout);
#endif

    scanf("%s", s + );
    n = strlen(s + );
    build_sa();
    build_height();

    ans = (long long)n*(n + )>>;
    for(int i = ; i <= n; i++)
        ans -= height[i];
    write(ans);

#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
#endif
    return ;
}