本文共 2346 字，大约阅读时间需要 7 分钟。

题意

给出长度为$n$的字符串,现在每个后缀都可以生成一个对应的序列

求这$n$个后缀生成的序列按照字典序排序的顺序,从小到大输出。

由于只有两个字母$a,b$,考虑到第一个出现的字母$a$和字母$b$在序列都是数字$0$

所以每个后缀的前缀序列一定是$01...10$的形式(中间可能没有$1$)

我们称之为$A$部分,其余部分称为$|B|$部分

$A$部分长度越小的,字典序越小(很显然吧,都是$01..10$的形式嘛)

$A$部分长度相同的,就都去掉$A$部分,比较后缀序列的大小

我们惊人的发现,去掉$A$部分后,$|B|$部分刚好是原串形成的序列的后缀!!!

问题是有些后缀没有$|B|$部分,那么该后缀的形式一定是$011111...1$的形式,设长度为$|A|$

那么比较大小的时候若$|A|$小于其他串的$|A|$,那么排在前面,否则排在后面

那么对于开头位置分别是$a,b,c$来说

实际上就是比较$a+|A|,b+|A|,c+|A|$的后缀序列大小,这部分可以由$sa$数组求得

于是问题就解决了

#include 
   
    using namespace std;const int maxn = 2e5+10;int n,m,x[maxn],y[maxn],sa[maxn],c[maxn],a[maxn],rk[maxn],las[maxn];char s[maxn];struct p{
   	int id,A,nxt,flag;	bool operator < (const p&t ) const	{
   		if( flag )	return A
    
     =1;i--)	sa[c[x[i]]--] = i;	for(int k=1;k<=n;k<<=1)	{
   		int num = 0;		for(int i=n-k+1;i<=n;i++)	y[++num] = i;		for(int i=1;i<=n;i++)	if( sa[i]>k )	y[++num] = sa[i]-k;		for(int i=0;i<=m;i++)	c[i] = 0;		for(int i=1;i<=n;i++)	++c[x[i]];		for(int i=1;i<=m;i++)	c[i] += c[i-1]; 		for(int i=n;i>=1;i--)	sa[c[x[y[i]]]--] = y[i], y[i] = 0;		swap(x,y);		x[sa[1]] = 1, num = 1;		for(int i=2;i<=n;i++)			x[sa[i]] = ( y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k] )?num:++num; 			if( num==n )	break;		m = num;//只有这么多种类型 	}	for(int i=1;i<=n;i++)	rk[sa[i]] = i;}int main(){
   	while( scanf("%d%s",&n,s+1 )!=EOF )	{
   		las['a'] = las['b'] = 0;		for(int i=1;i<=n;i++)		{
   			if( las[s[i]] )	a[i] = i-las[s[i]];			else	a[i] = 0;			las[s[i]] = i;		}		//	SA(n);		SA(n,x,y);		las['a'] = las['b'] = 0;		for(int i=n;i>=1;i--)		{
   			if( s[i]=='a' )			{
   				int l = las['b']-i+1;				if( las['b'] )				{
   					vec[i].flag = 0;					vec[i].nxt = i+l, vec[i].A = l;				}				else					vec[i].flag = 1,vec[i].A = n-i+1;								}			else			{
   				int l = las['a']-i+1;				if( las['a'] )				{
   					vec[i].flag = 0;					vec[i].nxt = i+l, vec[i].A = l;				}				else	vec[i].flag = 1,vec[i].A = n-i+1;			}			las[s[i]] = i; vec[i].id = i;		}		sort( vec+1,vec+1+n );		for(int i=1;i<=n;i++)		{
   			printf("%d ",vec[i].id);			rk[i] = sa[i] = x[i] = y[i] = c[i] = a[i] = 0;			vec[i].id = vec[i].flag = vec[i].A = vec[i].nxt = 0;		}		puts("");	}}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115268503 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！