书海扬帆的博客

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
66
67
68
69
// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=1e6+5;
int n;
char s[maxn];
struct Node
{
int first,second,id;
}a[maxn],b[maxn];
int cnt[maxn],rank[maxn],sa[maxn];

void getsa(const char *s)
{
int tot=0;
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++) cnt[s[i]]++;
for(int i=1;i<=128;i++) cnt[i]+=cnt[i-1];
for(int i=n;i>0;i--) sa[cnt[s[i]]--]=i;
for(int i=1;i<=n;i++)
{
if(s[sa[i]]==s[sa[i-1]]) rank[sa[i]]=tot;
else rank[sa[i]]=++tot;
}
for(int k=1;k<=n;k*=2)
{
for(int i=1;i<=n;i++)
{
a[i].first=rank[i];
if(i+k<=n) a[i].second=rank[i+k];
else a[i].second=0;
a[i].id=i;
}

memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++) cnt[a[i].second]++;
for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
for(int i=n;i>0;i--) b[cnt[a[i].second]--]=a[i];

memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++) cnt[b[i].first]++;
for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
for(int i=n;i>0;i--) a[cnt[b[i].first]--]=b[i];
tot=0;
for(int i=1;i<=n;i++)
{
if(a[i].first==a[i-1].first && a[i].second==a[i-1].second)
rank[a[i].id]=tot;
else rank[a[i].id]=++tot;
}
if(tot>=n) break;
}
for(int i=1;i<=n;i++)sa[rank[i]]=i;
}

int main()
{
int tot=0;
scanf("%s",s+1);
n=strlen(s+1);
getsa(s);
for(int i=1;i<=n;i++) cout<<sa[i]<<' ';
cout<<endl;
//system("pause");
return 0;
}

参考资料:《后缀数组——处理字符串的有力工具》,罗穗骞,2009国家集训队论文



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:730.1k