2744:子串
查看提交统计提示提问
总时间限制:
1000ms
内存限制:
65536kB
描述
现在有一些由英文字符组成的大小写敏感的字符串，你的任务是找到一个最长的字符串x，使得对于已经给出的字符串中的任意一个y，x或者是y的子串，或者x中的字符反序之后得到的新字符串是y的子串。
输入
输入的第一行是一个整数t (1 <= t <= 10)，t表示测试数据的数目。对于每一组测试数据，第一行是一个整数n (1 <= n <= 100)，表示已经给出n个字符串。接下来n行，每行给出一个长度在1和100之间的字符串。
输出
对于每一组测试数据，输出一行，给出题目中要求的字符串x的长度。
样例输入
2
3
ABCD
BCDFF
BRCD
2
rose
orchid
样例输出
2
2
查看 提交 统计 提示 提问
代码：
#include<cstdio>
#include<string.h>
int n;
char str[100][101];
char * strrev(char * s){
char * h = s,*t = s, ch;
while(*t++){}
t--; t--;
while(h < t){
ch = *h;
*h++ = *t;
*t-- = ch;
}
return s;
}
int maxSubStr(char * source){
int subLen = strlen(source),srcLen = strlen(source);
bool foundStr;
char subStr[101],revStr[101];
while(subLen > 0){
for(int i = 0; i <= srcLen - subLen; i++){
strncpy(subStr,source+i, subLen);
strncpy(revStr,source+i, subLen);
subStr[subLen] = revStr[subLen] = '\0';
strrev(revStr);
foundStr = true;
for(int j = 0; j < n; j++){
if(strstr(str[j],subStr) == NULL && strstr(str[j],revStr) == NULL){
foundStr = false;
break;
}
}
if(foundStr) return subLen;
}
subLen--;
}
return 0;
}
int main(){
int t,i, minLen, subLen;
char minStr[101];
scanf("%d",&t);
while(t--){
scanf("%d",&n);
minLen = 100;
for(i = 0; i < n; ++i){
scanf("%s",str[i]);
if(strlen(str[i]) < minLen){
strcpy(minStr,str[i]);
minLen = strlen(minStr);
}
}
subLen = maxSubStr(minStr);
printf("%d\n",subLen);
}
return 0;
}
