LCS2 – Longest Common Substring II

洛谷LCS2 – Longest Common Substring II

题目大意

给你一些字符串，求它们的最长公共子串。

字符串个数不超过$10$，每个字符串的长度不超过$100000$。

题解

可以先看看LCS – Longest Common Substring。

这题与上面那题类似，只不过要多一些操作。

首先，用第一个字符串建一个$SAM$，然后在$SAM$上面匹配其他的字符串，匹配的方式见上面这道题。

因为有多个字符串，所以不能只用$now$了。我们用$w[p].mx[i]$表示在用字符串$i$来在$SAM$上匹配时$SAM$的位置$p$上能够达到的最长的长度。

当然，如果一个点可以被匹配到，则这个点的祖先都可以被匹配到。所以每个点要对其子树取$max$，然后对自己的长度取$min$。这个操作我这边用的是拓扑排序来实现，当然其他方法也可以。

最后，对于$SAM$上的每一个位置$p$，求这个位置在每个字符串匹配后的最小值，即$w[p].mx[i]$的最小值，让$ans$对这个值取$max$。最后的$ans$即为答案。

code

#includeusing namespace std;const int N=100000;int s1,t1,cnt,siz=0,lst=0,ans=0,ct[N*2+5],r[N*2+5];char s[N+5],t[N+5];queue<int>q;struct node{int len,link,bz,mx[15];map<char,int>nxt;}w[N*2+5];void add(char c){int cur=++siz;w[cur].len=w[lst].len+1;int p;for(p=lst;p!=-1&&!w[p].nxt.count(c);p=w[p].link)w[p].nxt[c]=cur;if(p==-1) w[cur].link=0;else{int q=w[p].nxt[c];if(w[p].len+1==w[q].len) w[cur].link=q;else{int cl=++siz;w[cl].len=w[p].len+1;w[cl].link=w[q].link;w[cl].nxt=w[q].nxt;for(;p!=-1&&w[p].nxt[c]==q;p=w[p].link)w[p].nxt[c]=cl;w[q].link=w[cur].link=cl;}}lst=cur;}void find(){int p=0,now=0;for(int i=1;i<=t1;i++){char c=t[i];if(w[p].nxt.count(c)){p=w[p].nxt[c];++now;}else{for(;p!=-1&&!w[p].nxt.count(c);p=w[p].link);if(p!=-1){now=w[p].len+1;p=w[p].nxt[c];}else{now=0;p=0;}}w[p].mx[cnt]=max(w[p].mx[cnt],now);}}void gt(){for(int i=1;i<=siz;i++) ++ct[w[i].link];for(int i=1;i<=siz;i++){if(!ct[i]) q.push(i);}while(!q.empty()){int u=q.front();q.pop();r[++r[0]]=u;--ct[w[u].link];if(!ct[w[u].link]) q.push(w[u].link);}}void up(int c){for(int i=1;i<=siz;i++){int u=r[i];w[w[u].link].mx[c]=min(max(w[w[u].link].mx[c],w[u].mx[c]),w[w[u].link].len);}}int main(){scanf("%s",s+1);s1=strlen(s+1);w[0].link=-1;for(int i=1;i<=s1;i++) add(s[i]);gt();while(scanf("%s",t+1)!=EOF){t1=strlen(t+1);++cnt;find();up(cnt);}for(int i=1,now;i<=siz;i++){now=1e9;for(int j=1;j<=cnt;j++){now=min(now,w[i].mx[j]);}ans=max(ans,now);}printf("%d",ans);return 0;}