「BZOJ2946」[POI2000] 公共串

Description

给出几个由小写字母构成的单词,求它们最长的公共子串的长度。

任务:

读入单词

计算最长公共子串的长度

输出结果

 

Input

 

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

 

Output

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

 

Sample Input

3

abcb

bca

acbc

Sample Output

2 


/**************************************************************

    Problem: 2946

    User: ictsing

    Language: C++

    Result: Accepted

    Time:40 ms

    Memory:1444 kb

****************************************************************/

 

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

typedef unsigned long long ull;

const int mt = 2000+5 ;

char s[5][mt];

ull p[mt],f[5][mt],h[mt],hsh[mt],mark[mt];

ull bas=131;

int n;

int cnt,top;

int len[5];

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

      ch=getchar();

      if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

      num=num*10+ch-'0';

      ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int find(ull x)

{

    int l=1,r=cnt;

    while(l<=r)

    {

        int mid=(l+r)>>1;

        if(hsh[mid]==x) return mid;

        if(hsh[mid]>x) r=mid-1;

        else l=mid+1;

    }

    return 0;

}

bool judge(int x)

{

    cnt=0,top=0;

    for(int i=0;i+x<=len[0];i++)

        h[++top]=f[0][i+x]-f[0][i]*p[x];

    sort(h+1,h+top+1);

    for(int i=1;i<=top;i++)

        if(h[i]!=h[i-1]) hsh[++cnt]=h[i];

    memset(mark,0,sizeof(mark));

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

        for(int j=0;j+x<=len[i];j++)

        {

            ull pp=f[i][j+x]-f[i][j]*p[x];

            int x=find(pp);

            if(x!=0&&mark[x]==i-1) mark[x]=i;

        }

    for(int i=1;i<=cnt;i++)

        if(mark[i]==n-1) return 1;

    return 0;

}

int main()

{

    p[0]=1;

    for(int i=1;i<=2000;i++) p[i]=p[i-1]*bas;

    n=read();

    int lft=0,rgt=2000,ans=0;

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

    {

        scanf("%s",s[i]+1);

        len[i]=strlen(s[i]+1);

        f[i][0]=0;

        for(int j=1;j<=len[i];j++)

            f[i][j]=f[i][j-1]*bas+s[i][j];

        rgt=min(rgt,len[i]);

    }

    while(lft<=rgt)

    {

        int mid=(lft+rgt)>>1;

        if(judge(mid)) ans=mid,lft=mid+1;

        else rgt=mid-1;

    }

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

    return 0;

}

 


评论

热度(6)