社区讨论
萌新初学OI,求助
P3809【模板】后缀排序参与者 9已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @mi7wttpt
- 此快照首次捕获于
- 2025/11/21 04:54 4 个月前
- 此快照最后确认于
- 2025/11/21 06:35 4 个月前
这个SA哪里写错了啊qwq?
CPP#include <bits/stdc++.h>
#define il inline
const int maxn = 1e6 + 10;
using namespace std;
namespace Fast_Input {
template<class T> il void read(T& res) {
res = 0; char ch; bool sign = 0;
do { ch = getchar(); sign |= ch == '-'; } while(!isdigit(ch));
while(isdigit(ch)) res = (res << 1) + (res << 3) + (ch & 15),ch = getchar();
(sign) && (res = -res);
}
}
using Fast_Input::read;
int tax[maxn],rnk[maxn],SA[maxn],tp[maxn];
char s[maxn];
int n,m,i,j,k,len,typs;
il void Radix_Sort() {
memset(tax,0,sizeof(tax));
for(int i = 1;i <= n;i++) tax[rnk[tp[i]]]++;
for(int i = 1;i <= typs;i++) tax[i] += tax[i - 1];
for(int i = n;i >= 1;i--) SA[tax[rnk[tp[i]]]--] = tp[i];
return;
}
il void arr_swap(int* a,int* b) {
for(int i = 1;i <= len;i++) {
int t = a[i]; a[i] = b[i]; b[i] = t;
}
return;
}
int main() {
scanf("%s",s + 1); len = strlen(s + 1); typs = 122;
for(int i = 1;i <= len;i++) rnk[i] = s[i],tp[i] = i;
Radix_Sort();
for(int j = 1;j <= n;j <<= 1) {
int tot = 0;
for(int i = len - j + 1;i <= len;i++) tp[++tot] = i;
for(int i = len - j + 1;i <= len;i++) {
if(SA[i] > j) tp[++tot] = SA[i] - j;
}
Radix_Sort();
arr_swap(rnk,tp);
rnk[SA[1]] = 1; tot = 1;
for(int i = 2;i <= len;i++) {
rnk[SA[i]] = (tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + j] == tp[SA[i - 1] + j]) ? tot : ++tot;
}
if(tot == n) break; typs = tot;
}
for(int i = 1;i <= len;i++) printf("%d ",SA[i]);
return 0;
}
回复
共 11 条回复,欢迎继续交流。
正在加载回复...