电子商务网站建设考试试卷,东莞网站推广衣裙,云服务器怎么样做网站,美食分享网站怎么做正题
题目链接:https://www.luogu.com.cn/problem/SP1811 题目大意
求两个串的最长公共子串。 解题思路
对与第一个串首先构建一个SAMSAMSAM#xff0c;然后考虑让第二个串在上面匹配。
对于枚举的每个位置要在SAMSAMSAM上找一个节点使得它的后缀是枚举到的位置的后缀。所…正题
题目链接:https://www.luogu.com.cn/problem/SP1811 题目大意
求两个串的最长公共子串。 解题思路
对与第一个串首先构建一个SAMSAMSAM然后考虑让第二个串在上面匹配。
对于枚举的每个位置要在SAMSAMSAM上找一个节点使得它的后缀是枚举到的位置的后缀。所以对于当前节点如果有新加入的字符串的边就走过去如果没有我们就可以在parentparentparent树上往前跳因为跳到的节点代表的后缀是满足且仅满足这些位置的后缀是加入这个字符之前的后缀跳了之后取那个节点的lenlenlen就好了。
时间复杂度O(n)O(n)O(n) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N5e510;
int n,las,tot,len[N],fa[N];
char s[N];int ch[N][26],ans;
void add(int c){int plas;int nplastot;len[np]len[p]1;for(;p!ch[p][c];pfa[p])ch[p][c]np;if(!p)fa[np]1;else{int qch[p][c];if(len[p]1len[q])fa[np]q;else{int nqtot;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]fa[q];fa[q]fa[np]nq;for(;pch[p][c]q;pfa[p])ch[p][c]nq;}}return;
}
int main()
{lastot1;scanf(%s,s1);nstrlen(s1);for(int i1;in;i)add(s[i]-a);memset(s,0,sizeof(s));scanf(%s,s1);nstrlen(s1);int now1,L0;for(int i1;in;i){int cs[i]-a;if(ch[now][c])nowch[now][c],L;else{for(;now!ch[now][c];nowfa[now]);if(now)Llen[now]1,nowch[now][c];else L0,now1;}ansmax(ans,L);}printf(%d,ans);
}
