星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 SP1811 【LCS - Longest Common Substring】

posted on 2018-06-10 12:36:17 | under 题解 |

怎么没有人给这SB题写题解啊......
直接用第一个串建 $SAM$ ,然后第二串放在上面暴力匹配每一位: 如果当前有这个字符的转移就直接转移,如果没有就沿着 $parent$ 边上跳,直到有这个转移为止。
有几个小问题要注意一下:找到转移后你不能直接把当前答案设为 $len[nex[p][x]]$ 而是 $len[p]+1$ ,因为 $len$ 表示的是最大长度;如果一开始就找到转移只能 $++now$ ,因为这时你的这个转移并不保证长度是当前节点的最大长度。

#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);
}