A string is finite sequence of characters over a non-empty finite set Σ.
In this problem, Σ is the set of lowercase letters.
Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.
Now your task is simple, for two given strings, find the length of the longest common substring of them.
Here common substring means a substring of two or more strings.
将两个字符串连接成一个，中间加入分隔符，加入后缀自动机
在后缀链接上DP求子串出现次数
如果某个子串在A串和B串都出现过，那么可以用maxlen更新答案
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int tot=1,las=1,len1,len2,cur,siz[1000005][2],head[1000005],tot2,ans; char s1[250005],s2[250005]; struct SAM { int ch[27],fa,len; }sam[1000005]; struct Edge { int to,nxt; }edge[1000005]; inline int read() { int w=0,f=1; char ch=0; while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘)w=(w<<1)+(w<<3)+ch-‘0‘,ch=getchar(); return w*f; } void insert(int c) { int p=las,np=las=++tot; sam[np].len=sam[p].len+1,siz[np][cur]=1; for(;p&&!sam[p].ch[c];p=sam[p].fa) sam[p].ch[c]=np; if(!p) sam[np].fa=1; else { int q=sam[p].ch[c]; if(sam[q].len==sam[p].len+1) sam[np].fa=q; else { int nq=++tot; sam[nq]=sam[q],sam[nq].len=sam[p].len+1,sam[np].fa=sam[q].fa=nq; for(;p&&sam[p].ch[c]==q;p=sam[p].fa) sam[p].ch[c]=nq; } } } void dfs(int k) { for(int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; dfs(v),siz[k][0]+=siz[v][0],siz[k][1]+=siz[v][1]; } if(siz[k][0]&&siz[k][1]) ans=max(ans,sam[k].len); } int main() { scanf("%s",s1+1),scanf("%s",s2+1),len1=strlen(s1+1),len2=strlen(s2+1); for(int i=1;i<=len1;i++) insert(s1[i]-‘a‘); insert(26),cur=1; for(int i=1;i<=len2;i++) insert(s2[i]-‘a‘); for(int i=1;i<=tot;i++) edge[++tot2]=(Edge){i,head[sam[i].fa]},head[sam[i].fa]=tot2; dfs(0),printf("%d\n",ans); return 0; }
SP1811 LCS - Longest Common Substring
原文：https://www.cnblogs.com/JDFZ-ZZ/p/14218607.html
