# HDOJ

xiaoxiao2021-03-01  39

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 解题 报告： 先是找出里面长度最短的字符串，然后枚举出那个字符串的正向和逆向的字串，然后和他们对比，不过字串是从大到小找下去的，找到符合的即可了。 代码如下： Code: #include<iostream> #include<cstring> usingnamespacestd; constintMax(105); chardata[Max][Max]; charTemp_Data[Max]; intCheck_Data(inta,intb) { for(inti=0;i<a;i++) if(i!=b&&!strstr(data[i],Temp_Data))//其中strstr的功能是在串中查找指定字符串的第一次出现，如果没有就返回NULL return0; return1; } intmain() { intnum; cin>>num; intn; while(num--&&cin>>n) { intstate=0,length=-1; for(inti=0;i<n;i++) { cin>>data[i]; if(length==-1||strlen(data[i])<length)//找出长度最小的串并标记位置 { length=strlen(data[i]); state=i; } } //cout<<state<<endl; inttemp=length,flag=0;//flag用来标记是否已经找到了符合条件的最长子串 while(temp) { //正向字符串的子串 for(inti=0;i+temp<=length;i++) { for(intj=i,a=0;a<temp;j++,a++) Temp_Data[a]=data[state][j]; Temp_Data[a]='/0'; //cout<<Temp_Data<<endl; if(Check_Data(n,state)) { flag=1; break; } } if(flag) break; //逆向字符串的子串 for(i=length-1;i-temp>=-1;i--) { for(intj=i,a=0;a<temp;j--,a++) Temp_Data[a]=data[state][j]; Temp_Data[a]='/0'; if(Check_Data(n,state)) { flag=1; break; } //cout<<Temp_Data<<endl; } if(flag) break; temp--; } cout<<temp<<endl; } return0; }