SPOJ 694 - Distinct Substrings -- 后缀数组（不相同的子串个数）

SPOJ 694 - Distinct Substrings

• 原题链接：https://www.spoj.com/problems/DISUBSTR/
• VJ链接：https://vjudge.ppsucxtt.cn/problem/SPOJ-DISUBSTR

题意

求不相同的子串个数

思路

利用hei[]数组

字符串的所有子串就是 每一个后缀的所有前缀

每一个后缀的子串个数就是 子串的长度

排行 i 的后缀与前面相同的子串个数就是 hei[i]

所以 排行i的后缀不相同的子串个数就是 n - sa[i] + 1 - hei[i]

累加和就是所有不相同的子串

代码部分

注意一下多组输入就可以了，模板题

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdio.h>
#define mk make_pair
using namespace std;

const int N = 1e3+10;
int tax[N], tp[N], rk[N], sa[N], hei[N], n, m;
char a[N];

void rsort(){
    for(int i = 1; i <= m; i++) tax[i] = 0;
    for(int i = 1; i <= n; i++) tax[rk[i]]++;
    for(int i = 1; i <= m; i++) tax[i] += tax[i-1];
    for(int i = n; i >= 1; i--) sa[tax[rk[tp[i]]]--] = tp[i];
}

void getsa(){
    for(int i = 1; i <= n; i++) rk[i] = a[i], tp[i] = i;
    rsort();
    for(int l = 1, k = 1; k < n; l +=l ,m = k){
        k = 0;
        for(int i = n - l +1; i <= n; i++) tp[++k] = i;
        for(int i =1; i <= n; i++) if(sa[i] > l) tp[++k] = sa[i] - l;
        rsort(), swap(rk, tp), rk[sa[1]] = k = 1;
        for(int i = 2; i <= n; i++)
            rk[sa[i]] = (tp[sa[i]] == tp[sa[i-1]] && tp[sa[i]+l] == tp[sa[i-1] +l])? k:++k;
    } 
}

void gethei(){
    int k = 0;
    for(int i = 1; i <= n; i++){
        if(rk[i] == 1) continue;
        int j = sa[rk[i]-1]; if(k) k--;
        while(i+k <= n && j+k <= n && a[i+k] == a[j+k]) k++;
        hei[rk[i]] = k;
    }
}

int main(){
    int cas; cin>>cas;
    while(cas--){
        cin>>a+1;
        n = strlen(a+1);
        m = 122;
        getsa();
        gethei();

        int sum = 0;
        for(int i = 1; i <= n; i++){
            sum += n - sa[i]+1 - hei[i];
        }
        cout<<sum<<endl;
    }

    return 0;
}