【bzoj2946】[Poi2000]公共串

2015.06.17 08:20 Wed | 15次阅读 | 旧日oi | 固定链接 | 源码

Description

       给出几个由小写字母构成的单词,求它们最长的公共子串的长度。
任务:
l        读入单词
l        计算最长公共子串的长度
l        输出结果

题解

傻题。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 200005
char s[N];
int len;
struct SAM
{
    int son[N][26],len[N],fa[N];
    int rk[N],ans[N],v[N];
    int tot,last;
    void init()
    {
        last=tot=1;
    }
    void insert(int x)
    {
        int p=last,np=++tot;last=np;
        len[np]=len[p]+1;
        for(;p&&!son[p][x];p=fa[p]) son[p][x]=np;
        if(!p) fa[np]=1;
        else
        {
            int q=son[p][x];
            if(len[q]==len[p]+1) fa[np]=q;
            else
            {
                int nq=++tot;len[nq]=len[p]+1;
                memcpy(son[nq],son[q],sizeof(son[q]));
                fa[nq]=fa[q];fa[q]=fa[np]=nq;
                for(;p&&son[p][x]==q;p=fa[p]) son[p][x]=nq;
            }
        }
    }
    void work()
    {
        int l=strlen(s),lcs=0;
        for(int now,p=1,i=0;i<l;i++)
        {
            now=s[i]-'a';
            if(son[p][now])
            {
                lcs++;
                p=son[p][now];
                ans[p]=max(ans[p],lcs);
            }
            else
            {
                while(p&&!son[p][now]) p=fa[p];
                if(son[p][now])
                {
                    lcs=len[p]+1;
                    p=son[p][now];
                    ans[p]=max(ans[p],lcs);
                }
                else p=1,lcs=0;
            }
        }
        for(int i=tot;i;i--)
        {
            int k=rk[i];
            len[k]=min(len[k],ans[k]);
            ans[fa[k]]=max(ans[fa[k]],ans[k]);
            ans[k]=0;
        }
    }
    void solve(int L,int tim)
    {
        for(int i=1;i<=tot;i++) v[len[i]]++;
        for(int i=1;i<=L;i++) v[i]+=v[i-1];
        for(int i=tot;i;i--) rk[v[len[i]]--]=i;
        while(tim) scanf("%s",s),tim--,work();
        int mx=0;
        for(int i=1;i<=tot;i++) mx=max(mx,len[i]);
        printf("%d\n",mx);
    }
}sam;
int n;
int main()
{
    cin>>n;
    scanf("%s",s);len=strlen(s);
    sam.init();
    for(int i=0;i<len;i++) sam.insert(s[i]-'a');
    sam.solve(len,n-1);
    return 0;
}```