URAL 1590 – Bacon’s Cipher [后缀数组]

Mean

给你一个字符串,问这个字符串有多少个不同的字串

Analyse

这道题真是用尽了所有字符串的方法,首先想到的是字典树,把所有的字串插入到字典树中,最后输出一共有多少树的节点即可,但是这样会超内存。然后想到了字典树的左儿子右兄弟表示法,可以节省内存,然而这样每次查找儿子的时候需要遍历一遍儿子链表,导致TLE。

然后想到了哈希,这样就不会超时了,求出哈希表来之后,只有n2的复杂度,然而这样塞进一个set里面也会超时。于是想到了先放进vector再排序去重,可以减少一定时间,然而这样vector就存不下了,MLE。

直到最后才想到了后缀数组,知道了后缀串字典序排序,求出height数组来之后,就可以知道每个后缀与前一个后缀的最长公共前缀。这样最后统计求和一下就可以了。需要注意刘汝佳的模板使用的时候字符串后面需要补’$’

C++ Code

#include <bits/stdc++.h>
using namespace std;

struct SuffixArray {
    static const int maxn = 5120;
    int n, sa[maxn], rank[maxn], height[maxn], t[maxn], t2[maxn], c[maxn];
    char *s;
    SuffixArray() { clear(); }
    void setDate(char *str, int len) { s = str, n = len; }
    void clear() { n = 0; memset(sa, 0, sizeof(sa)); }
    void build_sa(int m = CHAR_MAX) {
        int i, *x = t, *y = t2;
        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-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[y[i]]]++;
            for(i = 0; 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, k = 0;
        for(i = 0; i < n; i++) rank[sa[i]] = i;
        for(i = 0; i < n; i++) {
            if(k) k--;
            int j = sa[rank[i]-1];
            while(s[i+k] == s[j+k]) k++;
            height[rank[i]] = k;
        }
    }
}sa;

char buf[5120];

int main() {
    scanf("%s", buf);
    int len = strlen(buf);
    buf[len] = '$';
    buf[++len] = NULL;
    sa.setDate(buf, len);
    sa.build_sa();
    sa.build_height();
    int cnt = 0;
    for(int i = 1; i < len; ++i)
        cnt += len - sa.sa[i] - 1 - sa.height[i];
    printf("%d\n", cnt);
    return 0;
}

欢迎留言