题解 SP1811 【LCS - Longest Common Substring】
teafrogsf
2018-06-10 12:36:17
怎么没有人给这~~SB~~题写题解啊......
直接用第一个串建$SAM$,然后第二串放在上面暴力匹配每一位:
如果当前有这个字符的转移就直接转移,如果没有就沿着$parent$边上跳,直到有这个转移为止。
有几个小问题要注意一下:找到转移后你不能直接把当前答案设为$len[nex[p][x]]$而是$len[p]+1$,因为$len$表示的是最大长度;如果一开始就找到转移只能$++now$,因为这时你的这个转移并不保证长度是当前节点的最大长度。
```cpp
#include<cstdio>
#include<cstring>
#define neko 1000010
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
typedef int arr[neko];
arr len,link;
int nex[neko][26];
namespace SAM
{
int ans=0,slen,cur,last,cnt=0;
void extend(char *s)
{
link[0]=-1;
slen=strlen(s)-1;
int p,q,clone,x;
f(i,0,slen)
{
len[cur=++cnt]=len[last]+1,x=s[i]-'a';
for(p=last;p!=-1&&(!nex[p][x]);p=link[p])nex[p][x]=cur;
if(p==-1)link[cur]=0;
else
{
q=nex[p][x];
if(len[q]==len[p]+1)link[cur]=q;
else
{
clone=++cnt;
len[clone]=len[p]+1;
link[clone]=link[q];
memcpy(nex[clone],nex[q],sizeof(nex[q]));
for(;p!=-1&&(nex[p][x]==q);p=link[p])nex[p][x]=clone;
link[cur]=link[q]=clone;
}
}
last=cur;
}
}
void solve(char *s)
{
slen=strlen(s)-1;
int p=0,x,now=0;
f(i,0,slen)
{
x=s[i]-'a';
//printf("%d %c %d %d\n",i,s[i],nex[p][x],len[nex[p][x]]);
if(nex[p][x])++now,p=nex[p][x];
else
{
for(;p!=-1&&(!nex[p][x]);p=link[p]);
if(p==-1)p=0,now=0;
else now=len[p]+1,p=nex[p][x];
}ans=chkmax(ans,now);
}printf("%d\n",ans);
}
}
char s[neko];
int main()
{
scanf("%s",s);
SAM::extend(s);
getchar();
scanf("%s",s);
SAM::solve(s);
}
```