提交记录 6643


用户 题目 状态 得分 用时 内存 语言 代码长度
Moon 1006. 【模板题】后缀排序 Wrong Answer 0 57.241 ms 3616 KB C++ 1.56 KB
提交时间 评测时间
2018-10-31 22:01:32 2020-08-01 00:47:54
//#include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <limits>
#include <map>
#include <vector>
#include <queue> 
#define P pair<int ,int >
#define pb push_back
#define LL long long
#define ft first
#define sd second
#define mp(x,y) make_pair(x,y)
#define db double
//#define int LL
using namespace std;
const int N   = 1e5+6;
//const int mod = ;
const int INF =numeric_limits<int >::max();

#define rep(i,x,y) for (int i=x;i<=y;++i)
void read(int &x)
{
	x=0;
	char ch=getchar();
	int f=1;
	while (!isdigit(ch)) (ch=='-'?f=-1:0),ch=getchar();
	while ( isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	x*=f;
}

struct suffix_array
{
	//static const int M=
	int n,m,cnt[N<<1],sa[N<<1],rk[N<<1],h[N<<1],tp[N<<1],p;
	int *x=rk,*y=tp;
	char str[N<<1];
	void Sort()
	{
		rep(i,0,m) cnt[i]=0;
		rep(i,1,n) ++cnt[x[y[i]]] ;
		rep(i,1,m) cnt[i]+=cnt[i-1];
		for (int i=n;i>=1;--i) sa[cnt[x[y[i]]]--]=y[i];
	}
	int cmp(int *f,int x,int y,int w){return f[x]==f[y]&&f[x+w]==f[y+w];}
	void SA()
	{
		rep(i,1,n ) x[i]=str[i],y[i]=i;
		m=256;Sort();
		for (int w=1;w<=n;w<<=1,m=p)
		{
			p=0;
			rep(i,n-w+1,n) y[++p]=i;
			rep(i,1,n) if (sa[i]>w) y[++p]=sa[i]-w;
			Sort();swap(x,y);
			x[sa[1]]=1;
			rep(i,2,n) x[sa[i]] =cmp(y,sa[i],sa[i-1],w) ? p:++p;
		}
		rep(i,1,n) rk[sa[i]]=i;
		for (int j,k=0,i=1;i<=n;h[rk[i++]]=k)
		  for ( k?--k:0 ,j=sa[rk[i]-1];str[j+k]==str[i+k];++k);
		  
	}
	
}A;

signed main()
{
	scanf("%s",A.str+1)	;
	A.n=strlen(A.str+1);
	A.SA();
	rep(i,1,A.n) printf("%d ",A.sa[i]);puts("");
	rep(i,2,A.n) printf("%d ",A.h[i]);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #136.98 us60 KBWrong AnswerScore: 0

Subtask #1 Testcase #238.2 us60 KBAcceptedScore: 100

Subtask #1 Testcase #336.86 us60 KBAcceptedScore: 0

Subtask #1 Testcase #442.72 us60 KBAcceptedScore: 0

Subtask #1 Testcase #541.4 us60 KBAcceptedScore: 0

Subtask #1 Testcase #643.54 us60 KBAcceptedScore: 0

Subtask #1 Testcase #757.241 ms3 MB + 196 KBWrong AnswerScore: -100

Subtask #1 Testcase #854.667 ms3 MB + 384 KBAcceptedScore: 0

Subtask #1 Testcase #956.745 ms3 MB + 248 KBWrong AnswerScore: 0

Subtask #1 Testcase #1035.7 ms2 MB + 136 KBAcceptedScore: 0

Subtask #1 Testcase #1135.147 ms2 MB + 176 KBWrong AnswerScore: 0

Subtask #1 Testcase #1242.292 ms3 MB + 444 KBAcceptedScore: 0

Subtask #1 Testcase #1342.417 ms3 MB + 544 KBAcceptedScore: 0

Subtask #1 Testcase #1455.079 ms3 MB + 276 KBAcceptedScore: 0

Subtask #1 Testcase #1554.363 ms3 MB + 292 KBAcceptedScore: 0

Subtask #1 Testcase #1642.18 ms3 MB + 444 KBWrong AnswerScore: 0

Subtask #1 Testcase #1742.141 ms3 MB + 444 KBAcceptedScore: 0

Subtask #1 Testcase #1842.486 ms3 MB + 444 KBAcceptedScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2025-07-03 12:54:42 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠