LINK

题意

给出长度为$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 <bits/stdc++.h>
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<t.A;
		if( t.flag )	return A<=t.A;
		if( A!=t.A )	return A<t.A;
		else	return rk[nxt]<rk[t.nxt];
	}
}vec[maxn];
//void SA(int n)
void SA(int n,int x[],int y[])
{
	int m = n;
	for(int i=1;i<=n;i++)	++c[x[i]=a[i]];
	for(int i=1;i<=m;i++)	c[i] += c[i-1];
	for(int i=n;i>=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("");
	}
}