题目描述

现在有一些由英文字符组成的字符串，你的任务是找到一个最长的字符串x，使得对于已经给出的字符串中的任意一个y，x或者是y的子串，或者x中的字符反序之后得到的新字符串是y的子串。（不区分大小写）

输入的第一行是一个整数t (1 <= t <= 10)，t表示测试数据的数目。对于每一组测试数据，第一行是一个整数n (1 <= n <= 100)，表示已经给出n个字符串。接下来n行，每行给出一个长度在1和100之间的字符串。

对于每一组测试数据，输出一行，给出题目中要求的字符串x的长度。

Sample Input

2

3

ABCD

BCDFF

BRCD

2

Rose

Orchid

Sample Output

2

2

代码

#include<stdio.h>
#include<string.h>

int main()
{
    char str[100][101],minstr[101],substr[101],revsubstr[101];
    unsigned int i,j,k,t,m,n,substrlen,found,minlen;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        minlen=101;
        for(i=0;i<n;i++)
        {
            scanf("%s",str[i]);
            for(k=0;str[i][k]!='\0';k++)
                if(str[i][k]>='A' && str[i][k]<='Z')
                    str[i][k]+=32;
            if(strlen(str[i])<minlen)
            {
                minlen=strlen(str[i]);
                m=i;
            }    
        }
        strcpy(minstr,str[m]);
        substrlen=minlen;
        while(substrlen>0)
        {
            for(i=0;i<=minlen-substrlen;i++)
            {
                strncpy(substr,minstr+i,substrlen);
                substr[substrlen]='\0';
                strncpy(revsubstr,minstr+i,substrlen);
                revsubstr[substrlen]='\0';
                strrev(revsubstr);
                found=1;
                for(j=0;j<n;j++)
                {
                    if(strstr(str[j],substr)==NULL && strstr(str[j],revsubstr)==NULL)
                    {
                        found=0;
                        break;
                    }
                }
                if(found)
                    break;
            }
            if(found)
                break;
            substrlen--;
        }
        printf("%d\n",substrlen);
    }
    return 0;
}