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

rose

orchid

Sample Output

题意：在给出的字符串中，找到在所有字符串中均出现的最长子串。

思路：先找出最短的字符串，再用其子串搜索，目的是优化运行；

因为要求出最长子串，首先从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;

}

巴特西

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

最新文章

热门文章