后缀数组入门题集

佚名 6年前 (2019-05-13) 随笔 911人围观抢沙发百度已收录

SPOJ 694

题意：求字符串的不相同子串

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题解：所有的子串（每一个子串一定是某一个后缀的前缀）总数是n*（n+1）/2 (基本排列组合（插空法）)，减去重复的子串即可，重复的子串是height数组的；

额，加个代码就是方便自己以后复制粘贴....

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN=20005;
char str[MAXN];
int s[MAXN];
int sa[MAXN], rak[MAXN], height[MAXN];
int t1[MAXN], t2[MAXN], c[MAXN];

bool cmp(int *r, int a, int b, int l)
{
    return r[a]==r[b] && r[a+l]==r[b+l];
}

void da(int str[], int n, int m)
{
    int i, j, p, *x=t1, *y=t2;
    for(i=0; i<m; i++) c[i]=0;
    for(i=0; i<n; i++) c[x[i]=str[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(j=1; j<=n; j<<=1)
    {
        p=0;
        for(i=n-j; i<n; i++) y[p++]=i;
        for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;

        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]]=cmp(y, sa[i-1], sa[i], j)? p-1:p++;
        if(p>=n) break;
        m=p;
    }
}

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

int main()
{
    //freopen("in.txt", "r", stdin);
    int T; cin>>T;
    while(T--)
    {
        scanf("%s", str);
        int n=strlen(str);
        for(int i=0; i<=n; i++)
            s[i]=str[i];

        da(s, n+1, 128);
        calheight(s, n);

        int ans=n*(n+1)/2;
        for(int i=2; i<=n; i++)
            ans-=height[i];
        printf("%d\n", ans);
    }
    return 0;
}