（KMP 字符串处理）Substrings -- hdu -- 1238

http://acm.hdu.edu.cn/showproblem.php?pid=1238

Substrings

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Description

You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.

Input

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string.

Output

There should be one line per test case containing the length of the largest string found.

Sample Input

ABCD

BCDFF

BRCD

rose

orchid

Sample Output

2 2

之前写个是完全的暴力写的，因为数据很小，暴力也没关系，这次用了KMP，有点小题大做的感觉，不过刚刚学，就当练习了。

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

#define MOD 10000

#define N 210

char s[N][N];

int Next[N];

void FindNext(char b[])

{

    int i=, j=-, blen=strlen(b);

    Next[] = -;

    while(i<blen)

    {

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

            Next[++i] = ++j;

        else

            j = Next[j];

    }

}

int KMP(char a[], char b[])

{

    int i=, j=;

    int alen=strlen(a), blen=strlen(b);

    FindNext(b);

    while(i<alen)

    {

        while(j==- || (a[i]==b[j] && i<alen && j<blen))

            i++, j++;

        if(j==blen)

            return ;

        j = Next[j];

    }

    return ;

}

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        int i, j, k, n, MinLen=, len;

        char ss[N];

        memset(s, , sizeof(s));

        scanf("%d", &n);

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

        {

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

            len = strlen(s[i]);

            if(len<MinLen)

            {

                MinLen = len;

                memset(ss, , sizeof(ss));

                strcpy(ss, s[i]);

            }

        }

        char a[N], b[N];

        int index=;

        for(i=MinLen; i>; i--)

        for(j=; j<=MinLen-i; j++)

        {

            memset(a, , sizeof(a));

            memset(b, , sizeof(b));

            strncpy(a, ss+j, i);

            strcpy(b, a);

            strrev(b);

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

            {

                if(KMP(s[k], a)== && KMP(s[k], b)==)

                    break;

            }

            if(k==n)

            {

                index = i;

                i=-, j=;

            }

        }

        if(index)

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

        else

            printf("0\n");

    }

    return ;

}

巴特西

（KMP 字符串处理）Substrings -- hdu -- 1238

最新文章

热门文章