【题意】
多串求LCS。
【思路】
主要是想找一下SAM的优越感 :) velui good
后缀数组划分height需要注意不少细节 <_<，然后不停debug
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; const int N = *+; char s[N],tmp[N];
int sa[N],c[N],t[N],t2[N],rank[N],height[N]; void build_sa(int m,int n) {
int i,k,*x=t,*y=t2;
for(i=;i<m;i++) c[i]=;
for(i=;i<n;i++) c[x[i]=s[i]]++;
for(i=;i<m;i++) c[i]+=c[i-];
for(i=n-;i>=;i--) sa[--c[x[i]]]=i;
for(k=;k<=n;k<<=) {
int p=;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=;i<m;i++) c[i]=;
for(i=;i<n;i++) c[x[y[i]]]++;
for(i=;i<m;i++) c[i]+=c[i-];
for(i=n-;i>=;i--) sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=; x[sa[]]=;
for(i=;i<n;i++)
x[sa[i]]=y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k]? p-:p++;
if(p>=n) break;
m=p;
}
}
void get_height(int n) {
int i,j,k=;
for(int i=;i<=n;i++) rank[sa[i]]=i;
for(int i=;i<n;i++) {
if(k) k--;
j=sa[rank[i]-];
while(s[j+k]==s[i+k]) k++;
height[rank[i]]=k;
}
} int flag[],cr[N];
bool can(int M,int n,int k) {
int kase=,cnt=;
flag[cr[sa[]]]=kase;
for(int i=;i<n;i++)
if(height[i]<M)
cnt=,flag[cr[sa[i]]]=++kase;
else {
int r=cr[sa[i]];
if(flag[r]!=kase) cnt++,flag[r]=kase;
if(cnt==k) return true;
}
return false;
} int main() {
int n; scanf("%d",&n);
int block=n,sz=;
for(int i=;i<n;i++) {
scanf("%s",tmp);
for(int j=;tmp[j];j++)
s[sz]=tmp[j],cr[sz++]=i;
s[sz]=--block,cr[sz++]=i;
} build_sa('z'+,sz);
get_height(sz); int L=,R=sz;
while(L<R) {
int M=L+(R-L+)/;
if(can(M,sz,n)) L=M;
else R=M-;
}
printf("%d",L);
return ;
}
SA
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; const int N = *+; char s[N];
int last,sz,fa[N],ch[N][],l[N],mn[N],mx[N];
int c[N],b[N]; void add(int x) {
int c=s[x]-'a';
int p=last,np=++sz; last=np;
mn[np]=l[np]=x+;
for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
if(!p) fa[np]=;
else {
int q=ch[p][c];
if(l[p]+==l[q]) fa[np]=q;
else {
int nq=++sz; mn[nq]=l[nq]=l[p]+;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q];
fa[np]=fa[q]=nq;
for(;q==ch[p][c];p=fa[p]) ch[p][c]=nq;
}
}
} int main() {
int n; scanf("%d",&n);
last=++sz;
scanf("%s",s);
for(int i=;s[i];i++) add(i);
for(int i=;i<=sz;i++) c[l[i]]++;
for(int i=;i<=strlen(s);i++) c[i]+=c[i-];
for(int i=;i<=sz;i++) b[c[l[i]]--]=i;
int ans=;
for(int i=;i<n;i++) {
scanf("%s",s);
int p=,len=;
for(int i=;s[i];i++) {
int c=s[i]-'a';
if(ch[p][c]) { len++; p=ch[p][c]; }
else {
while(p&&!ch[p][c]) p=fa[p];
if(!p) { len=; p=; }
else { len=l[p]+; p=ch[p][c]; }
}
mx[p]=max(mx[p],len);
}
for(int i=sz;i;i--) {
int p=b[i];
mn[p]=min(mn[p],mx[p]);
if(fa[p]) mx[fa[p]]=max(mx[fa[p]],mx[p]);
mx[p]=;
}
}
for(int i=;i<=sz;i++)
if(ans<mn[i]) ans=mn[i];
printf("%d",ans);
return ;
}
SAM