洛谷上编译错误,疑似内存问题,但不知道咋改,但是逻辑正确
#include<bits/stdc++.h>
#include<algorithm>
#define INF 0x3f3f3f3f
#define maxn 1000005
#define ll long long
using namespace std;
ll tot=1,las=1;
struct SAM{
int len=0;
int fa=0;
int endpos=0;
int order=1;
int ch[26]={0};
}pool[maxn<<1];
int lens[maxn<<1];
int fas[maxn<<1];
int endposes[maxn<<1];
void extend(int c)
{
int p=las;
int np=las=++tot;
pool[np].len=pool[p].len+1;
pool[np].endpos=1;
for(;p&&!pool[p].ch[c];p=pool[p].fa)//遍历后缀
pool[p].ch[c]=np;
if(!p)
pool[np].fa=1;
else
{
int q=pool[p].ch[c];
if(pool[q].len==pool[p].len+1)
{
pool[np].fa=q;
}
else
{
int nq=++tot;
pool[nq]=pool[q];
pool[nq].endpos=0;
pool[nq].len=pool[p].len+1;
pool[np].fa=pool[q].fa=nq;//插入新节点
for(;p&&pool[p].ch[c]==q;p=pool[p].fa)
pool[p].ch[c]=nq;
}
}
}
ll maxm(ll p1,ll p2)
{
if(p1<p2)
return p2;
else
return p1;
}
void cons(void)
{
for(int i=tot;i>=1;i--)
{
int d=pool[i].order;
int fad=fas[d];
endposes[fad]+=endposes[d];
}
ll ans=0;
for(int i=1;i<=tot;i++)
if(endposes[i]>1)
{
ans=maxm(ans,endposes[i]*lens[i]);
}
printf("%lld",ans);
}
bool cmp(struct SAM p1,struct SAM p2)
{
return p1.len<p2.len;
}
char Str[maxn];
int main()
{
scanf("%s",Str);
int len=strlen(Str);
for(int i=0;i<len;i++)
extend(Str[i]-'a');
for(int i=0;i<=tot;i++)
{
pool[i].order=i;
lens[i]=pool[i].len;
fas[i]=pool[i].fa;
endposes[i]=pool[i].endpos;
}
sort(pool+1,pool+tot+1,cmp);
cons();
system("pause");
}