提交记录 16152


用户 题目 状态 得分 用时 内存 语言 代码长度
ynycoding 1006. 【模板题】后缀排序 Wrong Answer 0 58.947 ms 3604 KB C++11 1.14 KB
提交时间 评测时间
2021-04-15 11:27:13 2021-04-15 11:27:17
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100005
int n, rk[N], sa[N], cnt[N], x[N], y[N], h[N];
char s[N];
inline void proc(char *s, int n)
{
	for(int i=1; i<=n; ++i) rk[i]=s[i]-'a'+1;
	for(int len=1; len<=n; len<<=1)
	{
		for(int i=1; i<=n; ++i) x[i]=rk[i], y[i]=((i+len<=n)?rk[i+len]:0);
		std::fill(cnt, cnt+std::max(n, 26)+1, 0);
		for(int i=1; i<=n; ++i) ++cnt[y[i]];
		for(int i=1; i<=std::max(n, 26); ++i) cnt[i]+=cnt[i-1];
		for(int i=1; i<=n; ++i) rk[cnt[y[i]]--]=i;
		std::fill(cnt, cnt+std::max(n, 26)+1, 0);
		for(int i=1; i<=n; ++i) ++cnt[x[i]];
		for(int i=1; i<=std::max(n, 26); ++i) cnt[i]+=cnt[i-1];
		for(int i=n; i; --i) sa[cnt[x[rk[i]]]--]=rk[i];
		for(int i=1, tp=0; i<=n; ++i) tp+=(x[sa[i]]!=x[sa[i-1]]||y[sa[i]]!=y[sa[i-1]]), rk[sa[i]]=tp;
	}
}
inline void gheight(void)
{
	for(int i=1, k=0; i<=n; ++i)
	{
		if(rk[i]==1) continue;
		if(k) --k;
		int j=sa[rk[i]-1];
		for(; i+k<=n&&j+k<=n&&s[i+k]==s[j+k]; ++k);
		h[rk[i]]=k;
	}
}
int main()
{
	scanf("%s", s+1);
	n=strlen(s+1);
	proc(s, n);
	gheight();
	for(int i=1; i<=n; ++i) printf("%d ", sa[i]);
	puts("");
	for(int i=2; i<=n; ++i) printf("%d ", h[i]);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #110.06 us40 KBWrong AnswerScore: -100

Subtask #1 Testcase #214.44 us44 KBAcceptedScore: 100

Subtask #1 Testcase #315.06 us44 KBAcceptedScore: 0

Subtask #1 Testcase #417.18 us44 KBAcceptedScore: 0

Subtask #1 Testcase #516.86 us44 KBAcceptedScore: 0

Subtask #1 Testcase #617.01 us44 KBAcceptedScore: 0

Subtask #1 Testcase #758.947 ms3 MB + 152 KBAcceptedScore: 0

Subtask #1 Testcase #858.651 ms3 MB + 340 KBAcceptedScore: 0

Subtask #1 Testcase #958.571 ms3 MB + 204 KBAcceptedScore: 0

Subtask #1 Testcase #1036.791 ms2 MB + 120 KBAcceptedScore: 0

Subtask #1 Testcase #1136.373 ms2 MB + 160 KBAcceptedScore: 0

Subtask #1 Testcase #1249.11 ms3 MB + 532 KBAcceptedScore: 0

Subtask #1 Testcase #1348.615 ms3 MB + 500 KBAcceptedScore: 0

Subtask #1 Testcase #1457.319 ms3 MB + 232 KBAcceptedScore: 0

Subtask #1 Testcase #1556.923 ms3 MB + 248 KBAcceptedScore: 0

Subtask #1 Testcase #1645.89 ms3 MB + 532 KBAcceptedScore: 0

Subtask #1 Testcase #1745.57 ms3 MB + 532 KBAcceptedScore: 0

Subtask #1 Testcase #1845.772 ms3 MB + 532 KBAcceptedScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 19:13:49 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用