HDU 5442 – Favorite Donut [后缀数组]

点击打开hdu题目链接

题意

有一个长度为N的字符串,找一个起点,可以正着或反着读一遍,问你怎么读字典序最大。

分析

2015年长春网络赛的题。暴力是铁定不行了。网上有后缀数组和最小表示法两种做法,前几天刚学了后缀数组,先用这题练练手。

首先正反向分别构造出长度为2×N的串,由于串相同时,取起点尽量往前的缘故,所以在正向串的最后补0,在反向串的最后补一个大于所有字母的字母。这样串相同时,起点小的rank值大。计算出sa数组后,找出rank值最大的起点。最后再加个比较即可。

C++代码

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

struct SuffixArray {
    static const int maxn = 40010;
    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;

const int maxn = 40010;
int n, pos1, pos2;
string a, b;
char s[maxn], s1[maxn], s2[maxn];

void init() {
    scanf("%d %s", &n, s);
    for(int i = 0; i < n; ++i)
        s1[i] = s1[i+n]= s[i];
    for(int i = 0; i < 2 * n; ++i)
        s2[2*n-i-1] = s1[i];
    s1[2*n] = 0;
    s2[2*n] = 'z' + 1;
    s1[2*n+1] = s2[2*n+1] = 0;
}

void solve() {
    sa.setDate(s1, 2 * n + 1);
    sa.build_sa();
    sa.build_height();
    pos1 = 0, pos2 = 0;
    for(int i = 0; i < n; ++i) {
        if(sa.rank[i] > sa.rank[pos1])
            pos1 = i;
    }
    a.clear();
    for(int i = 0; i < n; ++i)
        a.push_back(s1[i+pos1]);

    sa.setDate(s2, 2 * n + 1);
    sa.build_sa();
    sa.build_height();
    for(int i = 0; i < n; ++i) {
        if(sa.rank[i] > sa.rank[pos2])
            pos2 = i;
    }
    b.clear();
    for(int i = 0; i < n; ++i)
        b.push_back(s2[i+pos2]);
    pos2 = n - pos2 - 1;
}

int main() {
    // freopen("/home/kun/buffer/in", "r", stdin);
    int T; scanf("%d", &T);
    while(T--) {
        init();
        solve();
        if(a == b) {
            if(pos1 <= pos2) printf("%d %d\n", pos1 + 1, 0);
            else printf("%d %d\n", pos2 + 1, 1);
        } else if(a > b) {
            printf("%d %d\n", pos1 + 1, 0);
        } else {
            printf("%d %d\n", pos2 + 1, 1);
        }
    }
    return 0;
}

欢迎留言