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
56
57
58
59
60
61
62
63
64
65
|
#define del(x) sa[c[s[x]]--]=x
#define add(x) sa[c[s[x]]++]=x
void SA_sort(int *S,int n,int m,int *s,int *tp,int tot)
{
clr(sa,n+2);clr(c1,m+2);
R(i,1,n) c1[s[i]]++;
R(i,2,m) c1[i]+=c1[i-1];
cpy(c+1,c1+1,m+2);
L(i,1,tot) del(S[i]);
R(i,1,m+1) c[i]=c1[i-1]+1;
R(i,1,n) if(sa[i]>1&&tp[sa[i]-1]) add(sa[i]-1);
cpy(c+1,c1+1,m+2);
L(i,1,n) if(sa[i]>1&&!tp[sa[i]-1]) del(sa[i]-1);
}
void SA_IS(int n,int m,int *s,int *tp,int *pos)
{
int tot=0,cnt=0;int *S=s+n;//为了减小常数，这里直接取一段没有用过的地址而不是重新申请。
tp[n]=0;//为了方便，钦定最后一位是S型
L(i,1,n-1) tp[i]=(s[i]!=s[i+1])?s[i]>s[i+1]:tp[i+1];
rk[1]=0;
R(i,2,n) if(tp[i-1]==1&&!tp[i]) pos[++tot]=i,rk[i]=tot;else rk[i]=0;//求出所有LMS子串的端点
SA_sort(pos,n,m,s,tp,tot);//排序LMS子串
int u=0,p=0;
R(i,1,n) if(rk[sa[i]]) //去重，即unique
{
u=rk[sa[i]];
if(cnt<=1||pos[u+1]-pos[u]!=pos[p+1]-pos[p]) ++cnt;//一个减小常数的优化：如果两个LMS子串长度不一样，显然这两个子串不同
else
{
R(j,0,pos[u+1]-pos[u]) //暴力判断，注意这里如果某个字符对应的LMS后缀不同，也应当认为不同，因为如果首字母相同，L型后缀字典序一定大于S型
if(s[pos[u]+j]!=s[pos[p]+j]||tp[pos[u]+j]!=tp[pos[p]+j]) {++cnt;break;}//因为LMS子串长度不超过$O(N)$，所以暴力扫描复杂度是对的。
}
S[u]=cnt;//重新标号
p=u;
}
if(tot!=cnt) SA_IS(tot,cnt,S,tp+n,pos+n);//cnt相当于不相同数字个数，如果cnt==tot相当于所有数字两两不同，直接桶排序。为了方便，tp和pos也直接取一段没有用过的地址。
else R(i,1,tot) sa[S[i]]=i;
R(i,1,tot) S[i]=pos[sa[i]];//得到真正的排名（之前的标号排的是LMS子串，这里的排名是LMS后缀）。
SA_sort(S,n,m,s,tp,tot);////利用LMS子串得到真正的sa。
}
int ht[N];
void get_ht(int n)
{
R(i,1,n) rk[sa[i]=sa[i+1]]=i;
int k=0;
R(i,1,n)
{
if(k) --k;
while(s[i+k]==s[sa[rk[i]-1]+k]) ++k;
ht[rk[i]]=k;
}
}
signed main()
{
//fread(str+1,1,100000,stdin);n=strlen(str+1);
//while(!isalpha(str[n])) --n;
n=strlen(str+1);
R(i,1,n) s[i]=str[i]-'a'+2;
s[++n]=1;
//writeln(n);R(i,1,n) writesp(s[i]);puts("");
SA_IS(n--,28,s,tp,pos);
get_ht(n);
R(i,1,n) printf("%d ",sa[i]);cout<<endl;
return 0;
}
|