杭电-1238Substrings（爆搜）

ゝ一世哀愁。 2022-08-10 04:41 124阅读 0赞

# Substrings #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)**

Total Submission(s): 8626 Accepted Submission(s): 4001

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

猛地一看还以为是LCS，原来是个爆搜题！不会超时放心枚举！

找出最短的串，然后枚举这个串的所有子串和反串即可！

#include<cstdio>
    #include<cstring>
    #include<aLgorithm>
    #define INF 0x3f3f3f3f
    char map[110][110],s1[110],s2[110];
    int main()
    {
    	int N,k,i,j,m,n,ma,f,MAX;
    	scanf("%d",&N);
    	while(N--)
    	{
    		scanf("%d",&n);
    		ma=INF;
    		for(i=0;i<n;i++)
    		{
    			scanf("%s",map[i]);
    			int len=strlen(map[i]);
    			if(len<ma)
    			{
    				ma=len;
    				f=i;
    			}
    		}
    		MAX=0;
    		int flag=1;
    		for(i=0;i<ma;i++)
    		{
    			for(j=i;j<ma;j++)
    			{
    				for(k=i;k<=j;k++)
    				{
    					s1[k-i]=map[f][k];//正子串
    					s2[j-k]=map[f][k];//反子串
    				}
    				s1[j-i+1]=s2[j-i+1]='\0';
    				
    				int len3=strlen(s1);
    				for(k=0;k<n;k++)
    				{
    					if(!strstr(map[k],s1)&&!strstr(map[k],s2))//子串都没出现过
    					{
    						flag=0;
    						break;
    					}
    				}
    				if(len3>MAX&&flag)
    				MAX=len3;
    				flag=1;
    			}
    		}
    		printf("%d\n",MAX);
    	}
    	return 0;
    }