ACM-子串（字符串处理）

问题描述

有一些由英文字符组成的大小写敏感的字符串。请写一个程序，找到一个最长的字符串 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]=;//必须加 
			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;
}