Substrings 子字符串-----搜索，substrings-----

Substrings 子字符串-----搜索，substrings-----

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   題意：在給出的字符串中， 找到在所有字符串中均出現的最長子串。     思路 ：先找出最短的字符串，再用其子串搜索， 目的是優化運行；          因為要 求出最長子串， 首先從len長度的子串開始；          子串長度依次減小， 保證所求定為最長子串；           多函數的組合有利於將問題細化。              

#include <stdio.h>
#include <string.h>
#include<stdlib.h>
#define maxn 105
char lina[maxn];
char a[maxn][maxn];
int x;
void linstr ()  //找出長度最小的字串
{
    int i;
    int len = 10000, lens;
    lina[0]='\0';
    scanf("%d", &x);
    for (i = 0; i<x; i++)
    {
        scanf("%s", a[i]);
        int lens = strlen(a[i]);
        if (len>lens)
        {
            strcpy(lina, a[i]);
            len = lens;
        }
    }
	
}
int fin (char str[], char rts[]) //判斷所提取的子串是否在所有字符串中出現 
{
    int i;
	
    for (i = 0; i<x; i++)
    {
        if (strstr(a[i], str)==0 && strstr(a[i], rts)==0)
            return 0;
    }
    return 1;
}

int fuck ()
{
    int i, len, j;
    len = strlen (lina);
    for (i = len; i>0; i--)
    {
        for (j = 0; j+i<=len; j++)
		{
			char str[maxn]= {0}, rts[maxn];
                        strncpy(str, lina+j, i);  //將lina中第j個開始的i個字符cpy到str中
                        strcpy(rts, str);         
                        strrev(rts);              //倒置函數 為了方便看題才用的 好多oj不支持倒置函數 需要自己再寫一個函數完成倒置
                        if (fin(str, rts)==1)     //判斷str和他的倒置函數是否滿足條件
                              return i;
		}
    }
    return 0;
}
int main ()
{
    int n, num;
	
    scanf("%d", &n);
    while (n--)
    {
        linstr();
        num = fuck();
        printf("%d\n", num);
    }
    return 0;
}