社区讨论

萌新初学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 条回复,欢迎继续交流。

正在加载回复...