~~刚学一年多OI的萌新~~
by aminoas @ 2019-03-15 18:11:59
谁教教我啊，我快调死了
by 南方不败 @ 2019-03-15 18:12:59
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1000050;
int n,m=128,sa[maxn],rnk[maxn],y[maxn],c[150];
char s[maxn];
void sort1()
{
int i;
for (i=1;i<=n;i++)
c[rnk[i]=s[i]]++;
for (i=2;i<=m;i++)
c[i]+=c[i-1];
for (i=n;i>=1;i--)
sa[c[rnk[i]]--]=i;
}
void sort2()
{
int i;
for (i=1;i<=m;i++)
c[i]=0;
for (i=1;i<=n;i++)
c[rnk[i]]++;
for (i=2;i<=m;i++)
c[i]+=c[i-1];
for (i=n;i>=1;i--)
sa[c[rnk[y[i]]]--]=y[i],y[i]=0;
}
void getsa()
{
int i,k,p;
// for (i=1;i<=n;i++) rnk[i]=s[i],y[i]=i;
sort1();
for (k=1;;k<<=1)
{
p=0;
for (i=n-k+1;i<=n;i++)
y[++p]=i;
for (i=1;i<=n;i++)
if (sa[i]>k)
y[++p]=sa[i]-k;
sort2();
swap(rnk,y);
rnk[sa[1]]=p=1;
for (i=2;i<=n;i++)
rnk[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
if (p==n)
return;
m=p;
}
}
int main()
{
int i;
scanf("%s",s+1);
n=strlen(s+1);
getsa();
for (i=1;i<=n;i++)
printf("%d ",sa[i]);
return 0;
}
```
我剩下3个点RE死活调不出
by Doubleen @ 2019-03-15 19:13:02
SA=simulate annealing=模拟退火（雾
但愿没拼写错
by Social_Zhao @ 2019-03-15 19:13:50
@[Doubleen](/space/show?uid=56432) 你已经很强了
by 南方不败 @ 2019-03-15 21:40:49