LINK
题意
给出长度为 n n n的字符串,现在每个后缀都可以生成一个对应的序列
求这 n n n个后缀生成的序列按照字典序排序的顺序,从小到大输出。
由于只有两个字母 a , b a,b a,b,考虑到第一个出现的字母 a a a和字母 b b b在序列都是数字 0 0 0
所以每个后缀的前缀序列一定是 01...10 01...10 01...10的形式(中间可能没有 1 1 1)
我们称之为 A A A部分,其余部分称为 ∣ B ∣ |B| ∣B∣部分
A A A部分长度越小的,字典序越小(很显然吧,都是 01..10 01..10 01..10的形式嘛)
A A A部分长度相同的,就都去掉 A A A部分,比较后缀序列的大小
我们惊人的发现,去掉 A A A部分后, ∣ B ∣ |B| ∣B∣部分刚好是原串形成的序列的后缀!!!
问题是有些后缀没有 ∣ B ∣ |B| ∣B∣部分,那么该后缀的形式一定是 011111...1 011111...1 011111...1的形式,设长度为 ∣ A ∣ |A| ∣A∣
那么比较大小的时候若 ∣ A ∣ |A| ∣A∣小于其他串的 ∣ A ∣ |A| ∣A∣,那么排在前面,否则排在后面
那么对于开头位置分别是 a , b , c a,b,c a,b,c来说
实际上就是比较 a + ∣ A ∣ , b + ∣ A ∣ , c + ∣ A ∣ a+|A|,b+|A|,c+|A| a+∣A∣,b+∣A∣,c+∣A∣的后缀序列大小,这部分可以由 s a sa 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("");
}
}