题目描述

Description

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

Input

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

Output

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

Sample Input

3
abcb
bca
acbc

Sample Output

２

题目分析

二分出一个长度 然后搞一个二维map来存前n-1个串的每个长度的hash值 然后再枚举最后一个串所有mid长度的hash值 检测是否在n-1个串里都出现过即可

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int n;
char str[7][2010];
int len[10];
int seed=26,p=1000000009;
long long po[2010];
void init()
{
    po[0]=1;
    for(int i=1;i<=2000;i++) po[i]=po[i-1]*seed%p;
}
int minn=10000;
map<int,int> m[7];
int check(int mid)
{
    for(int i=1;i<=n;i++) m[i].clear();
    long long tmp=0;
    for(int i=1;i<n;i++)
    {
        tmp=0;
        for(int j=1;j<=mid;j++)
            tmp=(tmp*seed+str[i][j]-'a')%p;
        for(int j=mid;j<=len[i];j++)
            m[i][tmp]=1,tmp=(((tmp-po[mid-1]*(str[i][j+1-mid]-'a')%p+p)%p)*seed+(str[i][j+1]-'a'))%p;
    }
    tmp=0;
    for(int i=1;i<=mid;i++) tmp=(tmp*seed+str[n][i]-'a')%p;
    for(int i=mid;i<=len[n];i++)
    {
        int flag=1;
        for(int j=1;j<n;j++) if(m[j][tmp]==0) flag=0;
        if(flag) return 1;
        tmp=(((tmp-po[mid-1]*(str[n][i+1-mid]-'a')%p+p)%p)*seed+(str[n][i+1]-'a'))%p;
    }
    return 0;
}
int main()
{
    scanf("%d",&n);
    init();
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str[i]+1);
        len[i]=strlen(str[i]+1);
        minn=min(minn,len[i]);
    }
    if(n==1)
    {
        printf("%d",minn);
        return 0;
    }
    int l=0,r=minn+1,ans=0,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid)) ans=max(ans,mid),l=mid+1;
        else r=mid;
    }
    printf("%d",ans);
    return 0;
}