現有一些由英文字符組成的大小寫敏感的字符串。編寫一個程序，找到一個最長的字符串x，使得：對于已經給出的字符串中的任意一個y, x或者是y的子串、或者x中的字符反序之后得到的新字符串是y的子串。 形式化定義：給定 S={s1,…,sn}, 尋找一個x, S.T. ?y (y ?S ? (x?y ? x’?y)) ? ? z (?y (y ?S ? (z?y ? z’?y)) ? (x?z)) -> 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 ); //找到最短字符串中的最長子串長度新聞熱點
疑難解答
