New Distinct Substrings

题目大意

给定一个字符串，求本质不同的子串个数

题解

SA常见思想：每一个子串都是某个后缀的前缀
考虑每一个后缀的贡献，首先他拥有n - sa[i]个(我是用的模板中，sa[i]的大小是0....n-1)前缀，这些前缀有height[i]个跟sa[i-1]相同，要减去。剩下的部分不可能与sa[i-1]之前的想通了，不然sa[i]会排在sa[i-1]前面

不知为何，SA板子要在字符串最后加一个0.

背过就是了[doge

还要注意本题的字符集是小写字母（鬼知道样例是什么东西）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <cmath>

void swap(int &a, int &b){int tmp = a;a = b, b = tmp;}
void swap(int* &a, int* &b){int *tmp = a;a = b;b = tmp;}
int max(int a, int b){return a > b ? a : b;}
int min(int a, int b){return a < b ? a : b;}
void read(int &x)
{
    x = 0;char ch = getchar(), c = ch;
    while(ch < '0' || ch > '9') c = ch, ch = getchar();
    while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
    if(c == '-') x = -x;
}

const int INF = 0x3f3f3f3f;
const int MAXN = 50000 + 10;


struct SuffixArray
{
    int s[MAXN], sa[MAXN], rank[MAXN], height[MAXN];
    int t[MAXN], t2[MAXN], c[MAXN];
    int n;
    void clear(){n = 0;memset(sa, 0, sizeof(sa));}
    
    void build_sa(int m)
    {
        ++ n;
        int i,*x=t,*y=t2;
        for(i=0;i<m;++i) c[i]=0;
        for(i=0;i<n;++i) x[i]=s[i];
        for(i=0;i<n;++i) c[x[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-k;i<n;++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[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]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p-1:p++;
            if(p>=n) break;
            m=p;
        }
        -- n;
    }
    
    void build_height()
    {
        int i,j,k=0;
        for(i=1;i<=n;++i) rank[sa[i]]=i;
        for(i=0;i<n;++i)
        {
            if(k) k--;
            j=sa[rank[i]-1];
            while(s[i+k]==s[j+k]) k++;
            height[rank[i]]=k;
        }
    }
}A;

int t, ans;
char tmp[MAXN];

int main()
{   
    read(t);
    for(;t;-- t)
    {
        ans = 0;
        scanf("%s", tmp);
        A.s[0] = tmp[0] - 'a' + 1;
        for(A.n = 1;tmp[A.n];++ A.n) A.s[A.n] = tmp[A.n] - 'a' + 1;
        A.s[A.n] = 0;
        A.build_sa(30);
        A.build_height();
        
        //调试信息
        /*for(int i = 1;i <= A.n;++ i) 
            printf("sa[%d]:%s\n", i, tmp + A.sa[i]);
        for(int i = 1;i <= A.n;++ i)
        printf("height[%d]:%d\n", i, A.height[i]);  */
        
        for(int i = 1;i <= A.n;++ i)
            ans += A.n - A.sa[i] - A.height[i];
        printf("%d\n", ans);
    }
    return 0;
} 

SPOJ694 New Distinct Substrings

原文：https://www.cnblogs.com/huibixiaoxing/p/11272870.html