Substrings（KMP）

Substrings

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 11006		Accepted: 3827

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 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

2
3
ABCD
BCDFF
BRCD
2
rose
orchid

Sample Output

2
2 

Source

Tehran 2002 Preliminary

    题意：

    给出T（1~10）个case，每个case都给出一个N（1~100），后给出N个字符串，求出最长的公共子串，这个子串可以是原序或者逆序存在。

 

    思路：

    KMP。同样也是列举第一个串，注意理解题目中的“ 原序或者逆序其中之一 ”是什么意思。子串可以以原序或者逆序存在于剩下的N - 1个字符串中，说明在N - 1个字符串中可能含有逆序的子串，也可能存在原序的子串。而不是N - 1个字符串全部只包含原序或者逆序子串的其中之一。

 

    AC：

#include<stdio.h>
#include<string.h>
char str[105][105];
int n,maxnum;

void turn(int len,char *inve,char *orig)
{
    for(int i = 0;i < len;i++)
        inve[i] = orig[len - i - 1];
}

void get_next(int len,int *next,char *orig)
{
    int i = 0,j = -1;
    next[0] = -1;
    while(i < len)
    {
        if(j == -1 || orig[i] == orig[j]) next[++i] = ++j;
        else                              j = next[j];
    }
}

int kmp(char *orig,char *match,int *next)
{
    int len1 = strlen(match),len2 = strlen(orig);
    int i = 0,j = 0;
    while(i < len1 && j < len2)
    {
        if(j == -1 || match[i] == orig[j])
        {
            i++;
            j++;
        }
        else    j = next[j];
    }
    if(j == len2) return 1;
    return 0;
}

int main()
{
    int c,next[105],next1[105];
    char p[105],p1[105];
    scanf("%d",&c);
    while(c--)
    {
        scanf("%d",&n);
        maxnum = 0;
        for(int i = 1;i <= n;i++)
            scanf("%s",str + i);
        for(int i = 0;i < strlen(str[1]);i++)
            for(int j = 1;j <= strlen(str[1]) - i;j++)
        {
            int k;
            memset(p,0,sizeof(p));
            memset(p1,0,sizeof(p1));
            memset(next,0,sizeof(next));
            memset(next1,0,sizeof(next1));
            strncpy(p,str[1] + i,j);
            turn(j,p1,p);
            get_next(j,next,p);
            get_next(j,next1,p1);
            for(k = 2;k <= n;k++)
                if(!kmp(p,str[k],next) && !kmp(p1,str[k],next1)) break;
            if(k == n + 1 && j > maxnum)  maxnum = j;
        }
        printf("%d\n",maxnum);
    }
    return 0;
}