借楼宣传一下,同样在P5546过了,这题WA
用的SA
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+35;
int t[N],rk[N],h[N],sa[N],sec[N];
inline void sort(int *a,int n,int m)
{
for(int i=1;i<=m;++i) t[i]=0;
for(int i=1;i<=n;++i) ++t[rk[i]=a[i]];
for(int i=1;i<=m;++i) t[i]+=t[i-1];
for(int i=1;i<=n;++i) sa[t[rk[i]]--]=i;
for(int k=1;k<n;k<<=1)
{
int cnt=0;
for(int i=n;i>n-k;--i) sec[++cnt]=i;
for(int i=1;i<=n;++i) if(sa[i]>k) sec[++cnt]=sa[i]-k;
for(int i=1;i<=m;++i) t[i]=0;
for(int i=1;i<=n;++i) ++t[rk[sec[i]]];
for(int i=1;i<=m;++i) t[i]+=t[i-1];
for(int i=n;i;--i) sa[t[rk[sec[i]]]--]=sec[i],sec[i]=0;
swap(rk,sec);
rk[sa[1]]=cnt=1;
for(int i=2;i<=n;++i)
rk[sa[i]]=(sec[sa[i]]==sec[sa[i-1]]&&sec[sa[i]+k]==sec[sa[i-1]+k])?cnt:++cnt;
if(cnt==n) break;
m=cnt;
}
}
inline void geth(int *a,int n)
{
int j,k=0;
for(int i=1;i<=n;++i) rk[sa[i]]=i;
for(int i=1;i<=n;++i)
{
if(rk[i]==1) continue;
if(k) --k;
j=sa[rk[i]-1];
while(min(i,j)+k<=n&&a[i+k]==a[j+k]) ++k;
h[rk[i]]=k;
}
}
char s[N];
int a[N],id[N],n,cnt,ans,sum,js[N];
inline int z0(int x,int v){return x&(~(1<<v));}
inline int z1(int x,int v){return x|(1<<v);}
int q[N],head=1,tail;
inline void work()
{
sum=(1<<cnt)-1;int now=0;
for(int l=1,r=1;l<=n&&r<=n;++r)
{
while(h[q[tail]]>=h[r]&&head<=tail) --tail;
q[++tail]=r;
if(~id[sa[r]]&&++js[id[sa[r]]]==1) now=z1(now,id[sa[r]]);
while((~id[sa[l]]&&js[id[sa[l]]]>1)&&l<=r)
{
--js[id[sa[l]]],++l;
while(q[head]<=l&&head<=tail) ++head;
}
if(now==sum) ans=max(ans,h[q[head]]);
}
}
int T;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>T;
// while(T--){
while(cin>>s+1){
// cin>>s+1;
int len=strlen(s+1);
for(int i=1;i<=len;++i) a[++n]=s[i],id[n]=cnt;
a[++n]=127,id[n]=-1,++cnt;
}
sort(a,n,130),geth(a,n);
work();
cout<<ans<<endl;
}
```
by Nityacke @ 2023-03-20 15:42:41
@[Ethereal_shadow](/user/568716) 因为你一开始的时候末尾多加了个间隔符号,导致有可能算lcp的时候算了它。
所以做SA前n要减一
by Hanghang @ 2023-07-28 09:44:43