提交记录 20380


用户 题目 状态 得分 用时 内存 语言 代码长度
c20150005 1006. 【模板题】后缀排序 Wrong Answer 0 105.011 ms 4236 KB C++17 868 B
提交时间 评测时间
2023-10-13 21:22:41 2023-10-13 21:22:49

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
using ull=unsigned long long;
char ch[N];
int n,rk[N],sa[N],ht[N];
ull hsh[N],pw[N],p=131;
bool cmp(int a,int b){
	int fl=0;
	if(a>b)swap(a,b),fl=1;
	int l=0,r=n-b-1,ans=-1;
	while(r>=l){
		int mid=(l+r)>>1;
		if((hsh[a+mid]-hsh[a-1])*pw[b-a]==hsh[b+mid]-hsh[b-1])ans=mid,l=mid+1;
		else r=mid-1;
	}
	if(b+ans==n-1)return fl;
	return fl^(ch[a+ans+1]<ch[b+ans+1]);
}
int main(){
	cin>>ch;
	n=strlen(ch);
	pw[0]=1;
	for(int i=1;i<n;i++)pw[i]=pw[i-1]*p;
	for(int i=0;i<n;i++)hsh[i]=(ch[i]-28)*pw[i]+hsh[i-1];
	for(int i=0;i<n;i++)sa[i]=i;
	stable_sort(sa,sa+n,cmp);
	for(int i=0;i<n;i++)rk[sa[i]]=i,printf("%d ",sa[i]+1);
	puts("");
	for(int i=0,k=0;i<n;i++){
		if(rk[i]==0)continue;
		k-=!!k;
		while(ch[i+k]==ch[sa[rk[i]-1]+k])k++;
		ht[rk[i]]=k;
	}
	for(int i=1;i<n;i++)printf("%d ",ht[i]);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #136.83 us56 KBWrong AnswerScore: 0

Subtask #1 Testcase #237.37 us60 KBAcceptedScore: 0

Subtask #1 Testcase #336.75 us60 KBAcceptedScore: 0

Subtask #1 Testcase #441.81 us60 KBAcceptedScore: 0

Subtask #1 Testcase #541.51 us60 KBAcceptedScore: 0

Subtask #1 Testcase #642.61 us60 KBAcceptedScore: 0

Subtask #1 Testcase #785.322 ms3 MB + 784 KBAcceptedScore: 0

Subtask #1 Testcase #899.876 ms3 MB + 972 KBAcceptedScore: 0

Subtask #1 Testcase #995.77 ms3 MB + 836 KBAcceptedScore: 0

Subtask #1 Testcase #1059.768 ms2 MB + 524 KBAcceptedScore: 0

Subtask #1 Testcase #1162.649 ms2 MB + 564 KBAcceptedScore: 0

Subtask #1 Testcase #1252.62 ms4 MB + 140 KBAcceptedScore: 0

Subtask #1 Testcase #1371.861 ms4 MB + 108 KBAcceptedScore: 0

Subtask #1 Testcase #1497.219 ms3 MB + 864 KBAcceptedScore: 0

Subtask #1 Testcase #15105.011 ms3 MB + 880 KBAcceptedScore: 0

Subtask #1 Testcase #1661.463 ms4 MB + 140 KBAcceptedScore: 0

Subtask #1 Testcase #1767.946 ms4 MB + 140 KBAcceptedScore: 0

Subtask #1 Testcase #1868.404 ms4 MB + 140 KBAcceptedScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2025-08-02 15:11:42 | Loaded in 2 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠