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

2

3

ABCD

BCDFF

BRCD

2

rose

orchid

 

Sample Output:

2

2

题意：n个字符串，找出这n个字符串中连续相同的最大子序列，子串的逆序也可以。

#include
      
       #include
       
        const int N=110;char str[N][N], resouce[N];int n;void Init() ///在输入数据时找到最短的那条字符串，只有这样才能保证找到的子串有可能是公共子串{    int i;    scanf("%d", &n);    scanf("%s", str[0]);    strcpy(resouce, str[0]);    for (i = 1; i < n; i++)    {        scanf("%s", str[i]);        if (strlen(str[i]) < strlen(resouce))            strcpy(resouce, str[i]);    }}int Judge(char sub[], char resub[]) ///判断找到的子串和其逆序是否是其它字符串的子串{    int i;    for (i = 0; i < n; i++)    {        if (strstr(str[i], sub) == NULL && strstr(str[i], resub) == NULL)            return 0; ///只要在一个字符串中没有找到该子串和其逆序，则该子串不是公共子序列    }    return 1;}int Sub(){    int i, j, len1 = strlen(resouce), k, t;    char sub[N], resub[N];    for (i = len1; i >= 1; i--)    {        for (j = 0; i+j <= len1; j++) ///从最长的子串查找，只要找到了属于所有字符串的子串，最长公共子序列就是该子串，便可停止查找        {            memset(sub, 0, sizeof(sub)); ///最短字符串的子串            memset(resub, 0, sizeof(resub)); ///子串的逆序            k = 0;            strncpy(sub, resouce+j, i);            for (t = strlen(sub)-1; t >= 0; t--)                resub[k++] = sub[t];            resub[k] = '\0';            if (Judge(sub, resub))                return strlen(sub);        }    }        return 0;}int main (){    int T, len;    scanf("%d", &T);    while(T--)    {        memset(resouce, 0, sizeof(resouce));        Init();        len = Sub();        printf("%d\n", len);    }    return 0;}