bzoj 2946

时间：2024-05-23 12:05:32

Description

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

Input

文件的第一行是整数 n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。

Output

仅一行，一个整数，最长公共子串的长度。

Sample Input

3
abcb
bca
acbc

Sample Output

２
同poj3450，这里多一种SAM做法
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MN 200002

using namespace std;

struct po{

    int t[],f,l;

    po(){

        f=-;l=;

    }

}t[MN];

int num=,n,la=,T,MMH,p,m;

char s[];

int mmh[MN],mmh_[MN];

inline void add(int x){

    int p=++num,o,ne;

    t[p].l=t[la].l+;

    while (la!=-&&!t[la].t[x]) t[la].t[x]=p,la=t[la].f;

    if (la==-) t[p].f=;else{

        o=t[la].t[x];

        if (t[o].l==t[la].l+) t[p].f=o;else{

            ne=++num;

            t[ne]=t[o];

            t[ne].l=t[la].l+;

            t[o].f=t[p].f=ne;

            while (la!=-&&t[la].t[x]==o) t[la].t[x]=ne,la=t[la].f;

        }

    }

    la=p;

}

inline int max(int a,int b){return a>b?a:b;}

inline int min(int a,int b){return a<b?a:b;}

int main(){

    int i,j,k;

    scanf("%d",&T);

    scanf("%s",s);n=strlen(s);T--;

    for (i=;i<n;i++) add(s[i]-'a');

    memset(mmh,,sizeof(mmh));

    while (T--){

        memset(mmh_,,sizeof(mmh_));

        scanf("%s",s);

        n=strlen(s);

        p=;m=;

        for (i=;i<n;i++)

        if (t[p].t[s[i]-'a']){

            p=t[p].t[s[i]-'a'];mmh_[p]=max(mmh_[p],++m);

            for (k=p;t[k].f!=-;k=t[k].f) mmh_[t[k].f]=max(mmh_[t[k].f],min(mmh_[k],t[t[k].f].l));

        }else{

            while (p!=-&&!t[p].t[s[i]-'a']) p=t[p].f;

            if (p!=-) m=mmh_[p]+,p=t[p].t[s[i]-'a'],mmh_[p]=max(mmh_[p],m);else p=,m=;

            for (k=p;t[k].f!=-;k=t[k].f) mmh_[t[k].f]=max(mmh_[t[k].f],min(mmh_[k],t[t[k].f].l));

        }

        for (i=;i<=num;i++) mmh[i]=min(mmh[i],mmh_[i]);

    }

    MMH=;

    for (i=;i<=num;i++) MMH=max(MMH,mmh[i]);

    printf("%d\n",MMH);

}

24340 kb 356 ms C++/Edit 1804 B

相关文章