现有一些由英文字符组成的大小写敏感的字符串。编写一个程序，找到一个最长的字符串x，使得：对于已经给出的字符串中的任意一个y, x或者是y的子串、或者x中的字符反序之后得到的新字符串是y的子串。 形式化定义：给定 S={s1,…,sn}, 寻找一个x, S.T. y (y S (xy x’y)) z (y (y S (zy z’y)) (xz)) -> strlen(x) > strlen(z) 其中， s1,…,sn, x, z表示字符串； x’和z’分别表示x和z中的字符反序之后得到的新字符串； strlen(x) 和strlen(z)分别表示x和z的长度。
输入的第一行是一个整数t (1< t <5), t 表示测试数据的组数； 对于每一组测试数据，第一行是一个整数n (1< n <10), 表示已经给出n个字符串； 接下来n行，每行给出一个长度在1~50之间的字符串
对于每一组测试数据输出一行，给出问题描述中要求的字符串x的长度； 如果找不到符合要求的字符串，则输出0。
#include <stdio.h> #include <string.h> int t, n; char str[100][101]; //暂存字符串 int searchMaxSubString( char* source) { int subStrLen = strlen(source), sourceStrLen = strlen(source); int i, j; bool foundMaxSubStr; char subStr[101], revSubStr[101]; while( subStrLen > 0 ) //当子串长度大于0 { for( i = 0; i <= sourceStrLen - subStrLen; i++) //原长减子串长 { strncpy( subStr, source + i, subStrLen); //把原字符串的从第i个字符开始拷贝到子串 strncpy( revSubStr, source + i, subStrLen); //……拷贝到反子串 subStr[subStrLen] = revSubStr[subStrLen] = '/0'; //字符数组最后加结束符 strrev( revSubStr); //得到反子串 foundMaxSubStr = true; //将标志位设为1 for( j = 0; j < n; j++) //n为几个字符串 if( strstr(str[j], subStr) == NULL && strstr( str[j], revSubStr) == NULL) //判断subStr是否是str[j]的子串，如果不是 { foundMaxSubStr = false; break; } if( foundMaxSubStr) return (subStrLen); //题目要求仅得到子串长度即可 } subStrLen--; //子串长减1 } return 0; } int main(void) { int i, minStrLen, subStrLen; char minStr[101]; scanf("%d", &t); //输入组数 while( t--) //直到组全部完成 { scanf("%d", &n); //输入个数 minStrLen = 100; for( i = 0; i < n; i++) { scanf("%s", str[i]); //输入字符串 if( strlen(str[i]) < minStrLen) { strcpy( minStr, str[i]); minStrLen = strlen( str[i] ); //找到最短的字符串 } } subStrLen = searchMaxSubString( minStr ); //找到最短字符串中的最长子串长度 PRintf("%d/n", subStrLen); } return 0; }新闻热点
疑难解答
