Blue Jeans - POJ 3080（多串的共同子串）

题目大意：有M个串，每个串的长度都是60，查找这M个串的最长公共子串（连续的），长度不能小于3，如果同等长度的有多个输出字典序最小的那个。

 

分析：因为串不多，而且比较短，所致直接暴力枚举的第一个串的所有子串，比较暴力的做法，如果串的长度大一些就没法玩了。

代码如下：

====================================================================================

 

#include<stdio.h>

#include<string.h>

const int MAXN = ;

const int oo = 1e9+;

char s[MAXN][MAXN];

int next[MAXN];

void GetNext(char s[])

{

    int i=, j=-, N=strlen(s);

    next[] = -;

    while(i < N)

    {

        if(j==- || s[i]==s[j])

            next[++i] = ++j;

        else

            j = next[j];

    }

}

bool KMP(char a[], char s[])

{

    int i=, j=;

    int Na=strlen(a), Ns = strlen(s);

    while(i < Na)

    {

        while(j==- || (a[i]==s[j] && i<Na) )

            i++, j++;

        if(j == Ns)return true;

        j = next[j];

    }

    return false;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int i, j, len, M, MaxLen=;

        char ans[MAXN] = "Z";

        scanf("%d", &M);

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

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

        for(len=; len>=; len--)

        for(i=; i<=MaxLen-len; i++)

        {///枚举第一个串的所有子串

            char b[MAXN]={};

            strncpy(b, s[]+i, len);

            GetNext(b);

            for(j=; j<M; j++)

            {

                if(KMP(s[j], b) == false)

                    break;

            }

            if(j==M && strcmp(ans, b) > )

                strcpy(ans, b);

            if(ans[] != 'Z' && i==MaxLen-len)

                i=, len = ;///跳出循环

        }

        if(ans[] == 'Z')

            printf("no significant commonalities\n");

        else

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

    }

    return ;

}