@[敌敌畏](/space/show?uid=65602) 好巨啊
by miaojiexi @ 2018-12-14 13:40:50
**%%%ZJJ%%%**
by MZW_BG @ 2018-12-14 13:46:06
@[敌敌畏](/space/show?uid=65602) 好快啊
by lijianyangyf @ 2018-12-14 13:48:18
@[lijianyangyf](/space/show?uid=58164) 没错，我就是比你快400ms，哈哈哈哈哈哈哈（淫荡的笑声）
by 爱喝敌敌畏 @ 2018-12-14 13:48:52
可以借鉴一下sais的代码吗qwq……
一直想学但是没有看懂现在的网上的思路
by shadowice1984 @ 2018-12-14 13:50:36
```cpp
#include<cstdio>
#include<cstring>
#define N 2100000
#define NN 1100000
using namespace std;
int lbsa[NN],rbsa[NN],sa[N];
char sstt[NN];int str[N];
bool type[N];int cs[NN];
int qwq[NN],num[N];
inline bool pd(bool type[],int p){return (!type[p] && type[p-1]);}
inline bool ccmp(int st[],bool type[],int q,int p)//1是不像，0是像
{
do
{
if(st[q]!=st[p])return true;
q++;p++;
}while(!pd(type,q) && !pd(type,p));
return (!pd(type,q) || !pd(type,p) || st[q]!=st[p]);
}
void isort(int st[],bool type[],int cs[],int sa[],int n,int m)
{
rbsa[0]=lbsa[0]=cs[0];for(int i=1;i<=m;i++)rbsa[i]=cs[i],lbsa[i]=cs[i-1]+1;
for(int i=1;i<=n;i++)
{
if(sa[i]>1 && type[sa[i]-1])sa[lbsa[st[sa[i]-1]]++]=sa[i]-1;
}
for(int i=n;i>=1;i--)
{
if(sa[i]>1 && !type[sa[i]-1])sa[rbsa[st[sa[i]-1]]--]=sa[i]-1;
}
}
void get_sa(int sa[],int st[],bool type[],int cs[],int qwq[],int num[],int n,int m)
{
for(int i=1;i<=n;i++)cs[st[i]]++;
rbsa[0]=cs[0];for(int i=1;i<=m;i++)cs[i]+=cs[i-1],rbsa[i]=cs[i];
//处理cs数组，同时顺便把rbsa处理出来
for(int i=n-1;i>=1;i--)//默认type[n]=0
{
if(st[i]>st[i+1])type[i]=1;
else if(st[i]==st[i+1])type[i]=type[i+1];
}
int cnt=0,t=-1,last=0;
for(int i=2;i<=n;i++)
{
if(pd(type,i))qwq[++cnt]=i,sa[rbsa[st[i]]--]=i;
}
isort(st,type,cs,sa,n,m);
for(int i=1;i<=n;i++)
{
if(!pd(type,sa[i]))continue;
if(!last || ccmp(st,type,sa[i],last))t++;
num[sa[i]]=t;last=sa[i];
}
if(t<cnt-1)
{
for(int i=1;i<=cnt;i++)st[n+i]=num[qwq[i]];
get_sa(sa+n,st+n,type+n,cs+m+1,qwq+cnt,num+n,cnt,t);
}
else
{
for(int i=1;i<=cnt;i++)sa[n+num[qwq[i]]+1]=i;
}
memset(sa,0,(n<<2));
memcpy(rbsa,cs,(m<<4)+4);
for(int i=cnt;i>=1;i--)sa[rbsa[st[qwq[sa[i+n]]]]--]=qwq[sa[i+n]];
isort(st,type,cs,sa,n,m);
}
int main()
{
scanf("%s",sstt+1);int n=strlen(sstt+1)+1;
for(int i=1;i<n;i++)str[i]=sstt[i];
get_sa(sa,str,type,cs,qwq,num,n,125);
for(int i=2;i<n;i++)printf("%d ",sa[i]);
printf("%d\n",sa[n]);
return 0;
}
```
因为我现在还在做另外一些题，所以暂时不打注释，Sorry，还有，被luogu反作弊我可不管。
by 爱喝敌敌畏 @ 2018-12-14 13:56:10
@[shadowice1984](/space/show?uid=56384)
by 爱喝敌敌畏 @ 2018-12-14 13:56:13
@[shadowice1984](/space/show?uid=56384) 我博客有
博客地址：我luogu博客里有
by VCode @ 2018-12-14 14:39:39
@[VCode](/space/show?uid=50165)
哦哦哦十分感谢~
by shadowice1984 @ 2018-12-14 14:45:29