提交记录 16159


用户 题目 状态 得分 用时 内存 语言 代码长度
ynycoding 1006. 【模板题】后缀排序 Accepted 100 8.535 ms 4468 KB C++11 2.76 KB
提交时间 评测时间
2021-04-15 11:34:38 2021-04-15 11:34:42
#pragma GCC optimize("Ofast", "unroll-loops", "omit-frame-pointer", "inline", "-ftree-vectorize", "-fopt-info-vec-all")
#pragma GCC option("arch=native", "tune=native", "no-zero-upper")
#pragma GCC target("sse,sse2,sse3,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2")

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200005
namespace iobuff{
	const int LEN=1000000;
	char out[LEN+5];
	char *pout=out, *eout=out+LEN;
	inline void pc(char c)
	{
		pout==eout&&(fwrite(out, 1, LEN, stdout), pout=out);
		(*pout++)=c;
	}
	inline void flush()
	{ fwrite(out, 1, pout-out, stdout), pout=out; }
	template<typename T> inline void putint(T x, char div)
	{
		static char s[15];
		static int top;
		top=0;
		x<0?pc('-'), x=-x:0;
		while(x) s[top++]=x%10, x/=10;
		!top?pc('0'), 0:0;
		while(top--) pc(s[top]+'0');
		pc(div);
	}
}
using namespace iobuff;
int n, s[N], s1[N], sa[N], cnt[N], p[N], rk[N], idx[N];//type S:0 L:1
bool t[N];
#define pushl(x) sa[idx[s[x]]++]=x
#define pushs(x) sa[idx[s[x]]--]=x
inline void inducedsort(int *s, bool *t, int *sa, int *cnt, int n, int m, int *v, int top)
{
	std::fill(sa+1, sa+n+1, 0);
	memcpy(idx, cnt, sizeof(int)*(m+1));
	for(int i=top; i; --i) pushs(v[i]);
	for(int i=1; i<=m; ++i) idx[i]=cnt[i-1]+1;
	for(int i=1; i<=n; ++i)
	{
		int x=sa[i]-1;
		if(x&&t[x]) pushl(x);
	}
	memcpy(idx, cnt, sizeof(int)*(m+1));
	for(int i=n; i; --i)
	{
		int x=sa[i]-1;
		if(x&&!t[x]) pushs(x);
	}
}
void SAIS(int *s, bool *t, int *p, int *cnt, int n, int m)
{
	int top=0, *s1=s+n+1;
	t[n]=0;
	for(int i=1; i<=n; ++i) ++cnt[s[i]];
	for(int i=1; i<=m; ++i) cnt[i]+=cnt[i-1];
	for(int i=n-1; i; --i) t[i]=(s[i]>s[i+1]||(s[i]==s[i+1]&&t[i+1]));
	for(int i=2; i<=n; ++i) rk[i]=((t[i-1]&&!t[i])?(p[++top]=i, top):0);
	inducedsort(s, t, sa, cnt, n, m, p, top);
	int nm=0;
	for(int i=1, x=0, y=0; i<=n; ++i) if(x=rk[sa[i]])
	{
		if(!m||p[x+1]-p[x]!=p[y+1]-p[y]) ++nm;
		else
		{
			if(memcmp(s+p[x], s+p[y], sizeof(int)*(p[x+1]-p[x]+1))) ++nm;
//			for(int l=p[x], r=p[y]; l<=p[x+1]; ++l, ++r)
//				if(s[l]!=s[r]) { ++nm; break; }
		}
		y=x;
		s1[x]=nm;
	}
	if(nm<top) SAIS(s1, t+n+1, p+n+1, cnt+m+1, top, nm);
	else for(int i=1; i<=top; ++i) sa[s1[i]]=i;
	for(int i=1; i<=top; ++i) s1[i]=p[sa[i]];
	inducedsort(s, t, sa, cnt, n, m, s1, top);
}
char rs[N];
int h[N];
inline void gheight(void)
{
	for(int i=1; i<=n; ++i) rk[sa[i]]=i;
	for(int i=1, k=0; i<=n; ++i) if(rk[i]<n)
	{
		int j=sa[rk[i]+1];
		k=std::max(0, k-1);
		while(rs[i+k]==rs[j+k]) ++k;
		h[rk[i]]=k;
	}
}
int main()
{
	scanf("%s", rs+1);
	n=strlen(rs+1);
	for(int i=1; i<=n; ++i) s[i]=rs[i]-'a'+2;
	s[++n]=1;
	SAIS(s, t, p, cnt, n, 27);
	for(int i=1; i<n; ++i) sa[i]=sa[i+1];
	sa[n]=0;
	--n;
	for(int i=1; i<=n; ++i) putint(sa[i], ' ');
	pc('\n');
	gheight();
	for(int i=1; i<n; ++i) putint(h[i], ' ');
	pc('\n');
	flush();
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #113.7 us56 KBAcceptedScore: 0

Subtask #1 Testcase #216.56 us56 KBAcceptedScore: 100

Subtask #1 Testcase #316.91 us56 KBAcceptedScore: 0

Subtask #1 Testcase #415.91 us56 KBAcceptedScore: 0

Subtask #1 Testcase #515.85 us56 KBAcceptedScore: 0

Subtask #1 Testcase #613.82 us56 KBAcceptedScore: 0

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

Subtask #1 Testcase #88.535 ms4 MB + 16 KBAcceptedScore: 0

Subtask #1 Testcase #98.502 ms3 MB + 796 KBAcceptedScore: 0

Subtask #1 Testcase #105.446 ms2 MB + 492 KBAcceptedScore: 0

Subtask #1 Testcase #115.206 ms2 MB + 528 KBAcceptedScore: 0

Subtask #1 Testcase #124.723 ms3 MB + 856 KBAcceptedScore: 0

Subtask #1 Testcase #134.655 ms3 MB + 824 KBAcceptedScore: 0

Subtask #1 Testcase #145.059 ms3 MB + 548 KBAcceptedScore: 0

Subtask #1 Testcase #155.148 ms3 MB + 608 KBAcceptedScore: 0

Subtask #1 Testcase #165.327 ms4 MB + 276 KBAcceptedScore: 0

Subtask #1 Testcase #175.363 ms4 MB + 372 KBAcceptedScore: 0

Subtask #1 Testcase #185.282 ms4 MB + 344 KBAcceptedScore: 0


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