spoj Longest Common Substring (多串求最大公共子序列)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了spoj Longest Common Substring (多串求最大公共子序列)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2032字，纯文字阅读大概需要3分钟。
内容图文
题目链接：
https://vjudge.net/problem/SPOJ-LCS
题意：
最多10行字符串
求最大公共子序列
数据范围：
$1\leq |S| \leq100000$
分析：
让他们都和第一个字符串匹配，算出每个字符串与第一个字符串的，以$i$位置（i指的是在s1中的位置）结尾匹配的最大长度
与其它字符串的匹配取最小值
最后对所有位置取最大值
超时代码：（题限是236ms，这个代码跑2000ms没问题）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=500000*2+7;
char S[maxn];
char S1[maxn/2];
int ans[maxn/2];
int n,a,b,len1,len2;
struct suffixautomation
{
int mp[maxn*2][30],fa[maxn*2],ed,ct,len[maxn*2],minpos[maxn*2],maxpos[maxn*2],deg[maxn*2];
int res[maxn/2];
suffixautomation(){
for(int i=0;i<maxn*2;i++)minpos[i]=1e9,maxpos[i]=-1;
ed=ct=1;}
inline void ins(int c,int pos)
{
int p=ed;ed=++ct;minpos[ed]=maxpos[ed]=pos;len[ed]=pos;//先初始化size和len
for(;p&&mp[p][c]==0;p=fa[p]){mp[p][c]=ed;}//然后顺着parent树的路径向上找
if(p==0){fa[ed]=1;return;}int q=mp[p][c];//case1
if(len[p]+1==len[q]){fa[ed]=q;return;}//case2
len[++ct]=len[p]+1;//case 3
for(int i=1;i<=26;i++){mp[ct][i]=mp[q][i];}
fa[ct]=fa[q];fa[q]=ct;fa[ed]=ct;
for(int i=p;mp[i][c]==q;i=fa[i]){mp[i][c]=ct;}
}
void solve(){
for(int i=1;i<=ct;i++)deg[fa[i]]++;
queue<int>que;
for(int i=1;i<=ct;i++)if(deg[i]==0)que.push(i);
while(que.size()){
int x=que.front();
int y=fa[x];
que.pop();
minpos[y]=min(minpos[x],minpos[y]);
maxpos[y]=max(maxpos[x],maxpos[y]);
deg[y]--;
if(deg[y]==0)que.push(y);
}
for(int i=1;i<=ct;i++)
if(minpos[i]<=len1&&maxpos[i]>=len1+2)
res[minpos[i]]=max(res[minpos[i]],len[i]);
}
}sam,sam2;
int main()
{
// cout<<"acfvd"
for(int i=0;i<maxn/2;i++)ans[i]=1e9;
scanf("%s",S+1);
len1=strlen(S+1);
S[len1+1]=‘z‘+1;
while(scanf("%s",S1+1)==1){
len2=strlen(S1+1);
sam=sam2;
for(int i=len1+2;i<=len1+len2+1;i++)
S[i]=S1[i-len1-1];
for(int i=1;i<=len1+len2+1;i++)sam.ins(S[i]-‘a‘+1,i);
sam.solve();
for(int i=1;i<=len1;i++)
ans[i]=min(ans[i],sam.res[i]);
}
int res=0;
for(int i=1;i<=len1;i++)
if(ans[i]!=1e9)res=max(res,ans[i]);
printf("%d\n",res);
return 0;
}
原文：https://www.cnblogs.com/carcar/p/11631745.html
内容总结
以上是互联网集市为您收集整理的spoj Longest Common Substring (多串求最大公共子序列)全部内容，希望文章能够帮你解决spoj Longest Common Substring (多串求最大公共子序列)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。