链接
https://ac.nowcoder.com/acm/contest/5666/A
题意
对于字符串 $t_1t_2…t_k$
定义 $B(t_1t_2…t_k)=b_1b_2…b_k$
若存在 $t_j=t_i$ ($j<i$)，那么 $b_i=\min_{1\le j<i,t_j=t_i}{i-j}$
否则 $b_i=0$
将字符串 $S$ （由 “a”，”b” 组成）的所有后缀按照其对应的 $B$ 序列的字典序排序
思路
对于字符串 $T$，可发现 $B(T)=AD,A=01..10$，可发现 $A$ 的长度越大，$A$ 的字典序越大
我们可以 $O(n)$ 求出 $B(s_1s_2…s_k)$ 所有的 $A$ 的长度，易发现 $B(s_1s_2…s_k)$ 的 $D$ 为 $B(S)$ 的后缀，用 $SA$ 求 $B(S)$ 后缀的排序，可以将 $A$ 作为第一关键字排序，$D$ 作为第二关键字排序
注意：
对于类似 ‘’aaa’’ 的情况，我们需要在最后加一个 ‘b’，此时 $A=0110$，否则 $A=011$，在 $A$ 长度相等情况下，$011$ 明显是大于 $010$ 的
在第二关键字排序时，$D$ 可能为空，下标为 $len+1,len+2$，分别将排名赋值为 $0,-1$ 即可
官方题解
设 $C_i = \min_{j > i,s_j = s_i} {j - i}$，数组 $C$ 的后缀从小到大排序就是答案
Detailed proof can be found in “Parameterized Suffix Arrays for Binary Strings ” http://www.stringology.org/event/2008/p08.html
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char s[N];
int n,nxt[2],pre[2],a[N],b[N],res[N];
int m,p,sa[N],id[N],rk[N],oldrk[N<<1],cnt[N];
void init() {
for(int i=0;i<2;i++) nxt[i]=pre[i]=0;
memset(b,0,sizeof b);
for(int i=1;i<=n;i++) res[i]=i,a[i]=0;
}
void get_sa(int *s) {
m=300;
for(int i=1;i<=n;i++) cnt[i]=0;
for(int i=1;i<=n;i++) cnt[rk[i]=s[i]]++;
for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for(int i=n;i>=1;i--) sa[cnt[rk[i]]--]=i;
for(int w=1,p;w<n;w<<=1,m=p) {
p=0;
for(int i=n;i>n-w;i--) id[++p]=i;
for(int i=1;i<=n;i++) if(sa[i]>w) id[++p]=sa[i]-w;
for(int i=1;i<=m;i++) cnt[i]=0;
for(int i=1;i<=n;i++) cnt[rk[id[i]]]++;
for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for(int i=n;i>=1;i--) sa[cnt[rk[id[i]]]--]=id[i];
for(int i=1;i<=n;i++) oldrk[i]=rk[i];
p=0;
for(int i=1;i<=n;i++) rk[sa[i]]=((oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])?p:++p);
}
}
bool cmp(int x,int y) {
return a[x]<a[y]||a[x]==a[y]&&rk[x+a[x]]<rk[y+a[y]];
}
int main() {
while(~scanf("%d",&n)) {
scanf("%s",s+1);
init();
for(int i=1;i<=n;i++) {
if(pre[s[i]-'a']) b[i]=i-pre[s[i]-'a'];
pre[s[i]-'a']=i;
}
for(int i=n;i>=1;i--) {
if(!nxt[(s[i]-'a')^1]) a[i]=n-i+2;
else a[i]=nxt[(s[i]-'a')^1]-i+1;
nxt[s[i]-'a']=i;
}
get_sa(b);
rk[n+1]=0;
rk[n+2]=-1;
sort(res+1,res+1+n,cmp);
for(int i=1;i<=n;i++) printf("%d ",res[i]);
puts("");
}
return 0;
}
|