最长公共子串(LCS) lg SP1811

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

后缀自动机的一大用处就是求最长公共子串了

这道题的话题意就是给你两个字符串，求最长公共子串

做法的话是先使用一个字符串建立SAM，然后让另一个串在上面进行匹配

匹配的策略是优先匹配当前节点的下一个字符，如果没有可以匹配的，就沿着parent树向上跳，如果到根了，就重新初始化重新开始搜，如果不是根就往下跳，把len更新为node[p].len+1（这个是因为我只是比p节点的串长1，而不是完全匹配选一个节点的最长长度）

具体的解释放在代码中吧

#include<bits/stdc++.h>
using namespace std;
inline int read(){
int w=,f=;
char ch=getchar();
while(ch<''||ch>''){
if(ch=='-') f=-;
ch=getchar();
}
while(ch>=''&&ch<=''){
w=(w<<)+(w<<)+ch-;
ch=getchar();
}
return w*f;
}
int n,m,lst=,tot=;
int l1,l2;
long long size[];
struct Node{
int len,fa;
map<int,int> ch;//因为有的题字符集可能比较大，开个map其实还是比较舒服的
}node[];
inline void extend(int now){//这个建SAM的过程是常规操作
int p=lst;tot++;lst=tot;int np=tot;
node[np].len=node[p].len+;
while(p&&!node[p].ch[now]){
node[p].ch[now] = np;
p = node[p].fa;
}
if(!p) node[np].fa = ;
else{
int q = node[p].ch[now];
if(node[q].len == node[p].len + ){
node[np].fa=q;
}
else{
int nq=++tot;
node[nq]=node[q];
node[nq].len=node[p].len+;
node[np].fa = node[q].fa = nq;
while(p && node[p].ch[now] == q){
node[p].ch[now] = nq;
p = node[p].fa;
}
}
}
}
char s[],t[];int ans=;
int main(){
scanf("%s%s",s+,t+);int i,j,k;
l1=strlen(s+),l2=strlen(t+);
for(i=;i<=l1;i++){
extend(s[i]-'a'+);
}//建出第一个串的SAM
int p=;int len=;//初始化，让当前指针到根，长度设为0
for(i=;i<=l2;i++){
int now=t[i]-'a'+;
if(node[p].ch[now]){//匹配策略见我上面的注释
p=node[p].ch[now];len++;
}
else{
while(p&&!node[p].ch[now]){
p=node[p].fa;
}
if(!p){
p=;len=;
}
else{
len=node[p].len+;p=node[p].ch[now];
}
}
ans=max(ans,len);
}
cout<<ans<<endl;
return ;
}