POJ 1509 Glass Beads 题解《挑战程序设计竞赛》

POJ 1509 Glass Beads 

降临：在电影《降临》中，七肢桶使用了一种环形语言。给定一个环状字符串，求从哪个字符断开并反转后得到的字符串字典序最小？

4.7华丽地处理字符串 

后缀数组 

将环切断反转相当于将序列分割为两段再分别反转拼接，可以看做是将两个原序列拼接得到的新序列中的某个子串翻转后得到的序列。

这一点与书上类似：

所以思路也是类似的，将字符串拼接自己即可。求出后缀数组后，起始位置小于原字符串长度L的第一个下标即为答案（字符串为从该下标开始的长L的字符串的反转）。大于L的长度不够，等于L的可以用0替代。

只不过要注意可能有多个答案，需要选取最小的下标。比如对于aa，答案是1而不是2。

要做到这一点，不用大动干戈去求LCP，直接在末尾再加一个唯一的最大的字符Z即可。这样相当于告诉算法，把Z尽量往后放，于是i尽量小。

#include <cstdio>
#include <string>
#include <algorithm>

const int MAX_L = 10000;

char buffer[MAX_L + 1];

const int MAX_N = 2 * MAX_L + 1;
std::string S;
int n, k;
int sa[MAX_N + 1];  // sa[i] := 字典序为i的后缀的起始下标
int rank[MAX_N + 1], tmp[MAX_N + 1];

// 比较(rank[i], rank[i+k])和(rank[j], rank[j+k])
bool compare_sa(const int i, const int j)
{
    if (rank[i] != rank[j])
    {
        return rank[i] < rank[j];
    }
    return (i + k <= n ? rank[i + k] : -1) < (j + k <= n ? rank[j + k] : -1);
}
// 计算字符串S的后缀数组
void construct_sa()
{
    // 初始长度为1，rank直接取字符的编码
    for (int i = 0; i <= n; i++)
    {
        sa[i] = i;
        rank[i] = i < n ? S[i] : -1;
    }

    // 利用对长度为k的排序的结果对长度为2k的排序
    for (k = 1; k <= n; k <<= 1)
    {
        std::sort(sa, sa + n + 1, compare_sa);

        // 现在tmp中临时储存新计算的rank，再转存回rank中
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; i++)
        {
            tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
        }
        for (int i = 0; i <= n; i++)
        {
            rank[i] = tmp[i];
        }
    }
}

int solve()
{
    std::string str(buffer);
    const int L = str.length();
    str = str + str + (char) ('z' + 1); // 将环切断相当于将序列分割为两段再分别反转拼接，
    // 可以看做是将两个原序列拼接得到的新序列中的某个子串翻转后得到的序列

    S = str;
    n = S.length();
    construct_sa();

    for (int i = 0; i <= n; i++)
    {
        if (sa[i] < L)
        {
            return sa[i] + 1;
        }
    }

    return -1;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int T;
    scanf("%d ", &T);
    while (T--)
    {
        scanf(" %s ", buffer);
        printf("%d\n", solve());
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1509 Glass Beads 题解《挑战程序设计竞赛》