题目链接:https://www.luogu.com.cn/problem/P4051
题目大意:
给定一个长度为 \(n\) 的字符串 \(s\),每次将 \(s\) 的首字符取出放到末尾……
这样能得到 \(n\) 个字符串。
将这 \(n\) 个字符串按字典序排序,然后输出每个字符串末尾的字符。
解题思路:
将字符串 \(s\) 翻倍(\(s \rightarrow ss\)),然后求 \(sa\) 数组,然后按 \(sa[i]\) 从小到大输出合法的子串(因为大小增加了一倍,后一半的都是不合法的子串,忽略即可)。
示例程序:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, w, sa[maxn], rk[maxn], oldrk[maxn<<1];
char s[maxn];
int main() {
scanf("%s", s+1);
n = strlen(s+1);
strncpy(s+1+n, s+1, sizeof(char)*n);
n <<= 1;
for (int i = 1; i <= n; i++) sa[i] = i, rk[i] = s[i];
for (w = 1; w < n; w <<= 1) {
sort(sa+1, sa+n+1, [](int i, int j) {
return rk[i] == rk[j] ? rk[i + w] < rk[j + w] : rk[i] < rk[j];
});
memcpy(oldrk, rk, sizeof(int)*(n+1));
for (int i = 1, p = 0; i <= n; i++) {
if (oldrk[sa[i]] != oldrk[sa[i-1]] || oldrk[sa[i] + w] != oldrk[sa[i-1] + w])
p++;
rk[sa[i]] = p;
}
}
for (int i = 1; i <= n; i++)
if (sa[i] <= n/2)
putchar(s[sa[i] + n/2 - 1]);
return 0;
}
标签:字符,洛谷,题解,maxn,数组,P4051,字符串,sa
From: https://www.cnblogs.com/quanjun/p/17171407.html