省选专练之后缀自动机SPOJLCS2 - Longest Common Substring II
程序员文章站
2022-04-30 18:41:48
...
这个是陈老师证明SA不能解决的问题之一
但实际这更像广义SAM
但是普通SAM也能A
首先同两个串的类似直接建
但是用一个数组存下来当前节点的权值
但是我太菜了
这里又一个广义后缀自动机的思想:
同层可能不更新
所以你需要跑一次topsort然后更新,
实际也简单,因为parent树上的节点都是较短的,他们一定成立,跟新step为权值就好了
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=4e5+100;
char S[N];
struct SAM{
int LCS[N];
int ans[N];
int C[N];
int R[N];
struct Node{
int pre;
int step;
int vis[26];
}SA[N];
int cnt,last,now;
int LCSNOW;
inline void Insert(char C){
int p=last;
int np=++cnt;
last=np;
SA[np].step=SA[p].step+1;
for(;!SA[p].vis[C-'a'];p=SA[p].pre)SA[p].vis[C-'a']=np;
if(!p)SA[np].pre=1;
else{
int q=SA[p].vis[C-'a'];
if(SA[q].step==SA[p].step+1){
SA[np].pre=q;
}
else{
int nq=++cnt;
SA[nq].step=SA[p].step+1;
memcpy(SA[nq].vis,SA[q].vis,sizeof(SA[q].vis));
SA[nq].pre=SA[q].pre;
SA[q].pre=SA[np].pre=nq;
for(;SA[p].vis[C-'a']==q;p=SA[p].pre)SA[p].vis[C-'a']=nq;
}
}
}
void Getans(char C){
if(SA[now].vis[C-'a']){
now=SA[now].vis[C-'a'];
LCSNOW=LCSNOW+1;
}
else{
for(;now&&!SA[now].vis[C-'a'];now=SA[now].pre);
if(!now)now=1,LCSNOW=0;
else{
LCSNOW=SA[now].step+1;
now=SA[now].vis[C-'a'];
}
// cout<<now<<" "<<C<<" "<<LCS[Id][pos]<<'\n';
}
LCS[now]=max(LCS[now],LCSNOW);
// cout<<LCSNOW<<'\n';
}
void Solve(){
memset(ans,0x3f,sizeof(ans));
cnt=last=1;
scanf("%s",S+1);
int len,Id=0,maxlen;
len=strlen(S+1);
maxlen=len;
for(int i=1;i<=len;i++)Insert(S[i]);
for(int i=1;i<=cnt;i++)C[SA[i].step]++;
for(int i=1;i<=len;i++)C[i]+=C[i-1];
for(int i=1;i<=cnt;i++)R[C[SA[i].step]--]=i;
while(~scanf("%s",S+1)){
memset(LCS,0,sizeof(LCS));
++Id;
now=1;
LCSNOW=0;
len=strlen(S+1);
for(int i=1;i<=len;i++){
Getans(S[i]);
}
for(int i=cnt;i>=1;i--){
if(LCS[R[i]])LCS[SA[R[i]].pre]=SA[SA[R[i]].pre].step;
}
for(int i=cnt;i>=1;i--){
ans[i]=min(ans[i],LCS[i]);
}
}
int sum=-1;
for(int i=1;i<=cnt;i++){
// cout<<ans[i]<<'\n';
sum=max(sum,ans[i]);
}
cout<<sum<<'\n';
}
}Solution;
int main(){
// freopen("spoj1812.in","r",stdin);
Solution.Solve();
// cout<<1;
return 0;
}
上一篇: 过来吃我的豆腐吧