「JoyOI1860」后缀数组

2014年9月4日4,4346

描述 Description

我们定义一个字符串的后缀suffix(i)表示从s[i]到s[length(s)]这段子串。
后缀数组（Suffix array）SA[i]中存放着一个排列，满足suffix(sa[i])<suffix(sa[i+1]) 按照字典序方式比较
定义height[i]表示suffix(sa[i])与suffix(sa[i-1])之间的最长公共前缀长度，其中height[1]=0
你的任务就是求出SA和height这两个数组。字符串长度<=200000

输入格式 InputFormat

一行，为描述中的字符串（仅会出现小写字母）

输出格式 OutputFormat

共两行，每行n个数，第一行为sa[i]，第二行为height[i]，其中每行的数均用空格隔开

样例输入 SampleInput

aabaaaab

样例输出 SampleOutput

4 5 6 1 7 2 8 3
0 3 2 3 1 2 0 1

题解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#define inf 2000000000
#define N 200005
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
char ch[N];
int a[N],h[N];
int v[N];
int sa[2][N],rk[2][N];
int p,q,k;
void calsa(int sa[N],int rk[N],int SA[N],int RK[N])
{
	for(int i=1;i<=n;i++)v[rk[sa[i]]]=i;
	for(int i=n;i;i--)
		if(sa[i]>k)
			SA[v[rk[sa[i]-k]]--]=sa[i]-k;
	for(int i=n-k+1;i<=n;i++)SA[v[rk[i]]--]=i;
	for(int i=1;i<=n;i++)
		RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);
}
void work()
{
	p=0,q=1;
	for(int i=1;i<=n;i++)v[a[i]]++;
	for(int i=1;i<=30;i++)v[i]+=v[i-1];
	for(int i=1;i<=n;i++)
		sa[p][v[a[i]]--]=i;
	for(int i=1;i<=n;i++)
		rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);
    for(k=1;k<n;k<<=1)
	{
		calsa(sa[p],rk[p],sa[q],rk[q]);
		swap(p,q);
	}
}
void geth()
{
	k=0;
	for(int i=1;i<=n;i++)
		if(rk[p][i]==1)h[rk[p][i]]=0;
		else 
		{
			int j=sa[p][rk[p][i]-1];
			while(a[i+k]==a[j+k])k++;
			h[rk[p][i]]=k;if(k>0)k--;
		}
}
int main()
{
	scanf("%s",ch+1);n=strlen(ch+1);
	for(int i=1;i<=n;i++)a[i]=ch[i]-'a'+1;
	work();
	geth();
	for(int i=1;i<=n;i++)printf("%d ",sa[p][i]);
	puts("");
	for(int i=1;i<=n;i++)printf("%d ",h[i]);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<cmath>

#include<algorithm>

#include<map>

#define inf 2000000000

#define N 200005

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

char ch[N];

int a[N],h[N];

int v[N];

int sa[2][N],rk[2][N];

int p,q,k;

void calsa(int sa[N],int rk[N],int SA[N],int RK[N])

{

for(int i=1;i<=n;i++)v[rk[sa[i]]]=i;

for(int i=n;i;i--)

if(sa[i]>k)

SA[v[rk[sa[i]-k]]--]=sa[i]-k;

for(int i=n-k+1;i<=n;i++)SA[v[rk[i]]--]=i;

for(int i=1;i<=n;i++)

RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);

}

void work()

{

p=0,q=1;

for(int i=1;i<=n;i++)v[a[i]]++;

for(int i=1;i<=30;i++)v[i]+=v[i-1];

for(int i=1;i<=n;i++)

sa[p][v[a[i]]--]=i;

for(int i=1;i<=n;i++)

rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);

for(k=1;k<n;k<<=1)

{

calsa(sa[p],rk[p],sa[q],rk[q]);

swap(p,q);

}

void geth()

{

k=0;

for(int i=1;i<=n;i++)

if(rk[p][i]==1)h[rk[p][i]]=0;

else

{

int j=sa[p][rk[p][i]-1];

while(a[i+k]==a[j+k])k++;

h[rk[p][i]]=k;if(k>0)k--;

}

int main()

{

scanf("%s",ch+1);n=strlen(ch+1);

for(int i=1;i<=n;i++)a[i]=ch[i]-'a'+1;

work();

geth();

for(int i=1;i<=n;i++)printf("%d ",sa[p][i]);

puts("");

for(int i=1;i<=n;i++)printf("%d ",h[i]);

return 0;

}

« 「BZOJ1692」[Usaco2007 Dec] 队列变换「BZOJ2251」[2010BJ Wc] 外星联络 »

heoi2015

大神从哪里学的后缀数组，能不能给个地址或者资料

hzwer

后缀数组处理字符串的有力工具

conic

你的代码TLE了..你当年做了什么让它A掉的..

数据加强过了O.O……

conic

我已换fgets读入和putchar输出效率提高了20多倍

翁家翌

应该用fread和fwrite才是正确姿势= =

hzwer.com _ Home | http://hzwer.com

「JoyOI1860」后缀数组

分类目录

热门文章

Myfriends

近期评论