问题描述
有一些由英文字符组成的大小写敏感的字符串。请写一个程序,找到一个最长的字符串 x,使得:对于已经给出的字符串中的任意一个 y, x 或者是 y 的子串、或者 x 中的字符反序之后得到的新字符串是 y 的子串。
输入数据
输入:输入的第一行是一个整数 t (1 <= t <= 10), t 表示测试数据的数目。对于每一组测试数据,第一行是一个整数 n (1 <= n <= 100),表示已经给出 n 个字符串。接下来 n 行,每行给出一个长度在 1 和 100 之间的字符串。
输出要求
输出:对于每一组测试数据,输出一行,给出题目中要求的字符串 x 的长度;如果找不到符合要求的字符串,则输出 0。
输入样例
2
3
ABCD
BCDFF
BRCD
2
rose
orchid
输出样例
2
2
问题分析
假设 x0 是输入的字符串中最短的一个, x 是所要找的字符串, x'是 x 反序后得到的字符串。显然,要么 x 是 x0 的子串、要么 x'是 x0 的子串。因此,只要取出 x0 的每个子串 x,判断 x是否满足给定的条件,找到其中满足条件的最长子串即。
解决方案
每输入一组字符串后,首先找到其中最短的字符串 x0。然后根据 x0 搜索满足条件的子字符串。对 x0 的各子字符串从长到短依次判断是否满足条件,直到找到一个符合条件的子字符串为止。此问题的关键有两点:
1. 搜索到 x0 的每个子字符串,并且根据子字符串的长度从长到短开始判断,不要遗漏了任何子字符串。
2. 熟练掌握下列几个字符串处理函数,确保程序代码简洁、高效。
strlen:计算字符串的长度
strncpy:复制字符串的子串
strcpy:复制字符串
strstr:在字符串中寻找子字符串
strrev:对字符串进行反序
参考程序
#include <iostream>
#include <cstring>
using namespace std;
int t,n;
char str[100][101];
int searchMaxSubString(char* source){
int subStrLen,sourceStrLen;
int i,j;
bool foundMaxSubStr;
char subStr[101],revSubStr[101];
subStrLen = sourceStrLen = strlen(source);
while(subStrLen > 0){
//搜索不同长度的子串,从最长的子串开始搜索
for(i=0;i<=sourceStrLen - subStrLen;i++){
//搜索长度为 subStrLen 的全部子串
strncpy(subStr,source+i,subStrLen);
strncpy(revSubStr,source+i,subStrLen);
subStr[subStrLen]=revSubStr[subStrLen]='\0';//'\0'必须加
strrev(revSubStr);//反转字符串
foundMaxSubStr = true;
//判断是否存在子串
for(j=0;j<n;j++){
//不存在返回NULL
if(strstr(str[j],subStr)==NULL && strstr(str[j],revSubStr)==NULL){
foundMaxSubStr = false;
break;
}
}
if(foundMaxSubStr){
return subStrLen;
}
}
subStrLen--;
}
return 0;
}
int main()
{
int i,minStrLen,subStrLen;
char minStr[101];
cin>>t;
while(t--){
cin>>n;
minStrLen = 100;
for(i=0;i<n;i++){
cin>>str[i];
//寻找输入字符串中的最短字符串
if(strlen(str[i])<minStrLen){
strcpy(minStr,str[i]);
minStrLen = strlen(str[i]);
}
}
//搜索满足条件的最长字符串
subStrLen = searchMaxSubString(minStr);
cout<<subStrLen<<endl;
}
return 0;
}