题解 SP1811 【LCS - Longest Common Substring】

teafrogsf

2018-06-10 12:36:17

Solution

怎么没有人给这~~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); } ```