解题报告 之 POJ1226 Substrings
Description
You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.
Input
The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string.
Output
There should be one line per test case containing the length of the largest string found.
Sample Input
2
3
ABCD
BCDFF
BRCD
2
rose
orchid
Sample Output
2
2
题目大意：给你一堆字符串，大小写敏感，求他们的最大公共子串（或反转子串），即在每个字符串中，这个子串正序或者逆序出现均可。输出最长公共子串（反转子串）长度。比如样例1的结果就是CD（DC）=2。
分析：这道题是很简单的，暴力解决，不涉及字符串高端算法。具体做法先到最短字符串，公共子串必然出自它的某个子串。然后遍历最短字符串的所有子串，去逐一验证即可，因为n才100。个人感觉用string比char*方便，大家看自己的习惯。string::npos表示find没找到该子串。关于rbegin和rend和string（...）的用法自行百度C++ string。
上代码：
#include
#include
#include
using namespace std; const int INF = 0x3f3f3f3f; string str[110]; int main() { int kase,n; int minl=INF; int minpos; cin >> kase; while(kase--) { minl = INF; cin >> n; for(int i = 0; i < n; i++) { cin >> str[i]; if(str[i].length() < minl) { minl = str[i].length(); minpos = i; } } string key = str[minpos]; string tem, rev; for(int i = minl; i >= 1; i--) //取字符串长度 { for(int j = 0; j + i -1 < minl; j++) { tem = string( key.begin() + j, key.begin() + j + i ); rev = string( tem.rbegin(), tem.rend() ); bool flag = true; for(int k = 0; k < n; k++) { if(str[k].find( tem ) == string::npos && str[k].find( rev ) == string::npos) { flag = false; break; } } if(flag) { printf( "%d\n", i ); goto here; } } } printf( "0\n" ); here:; } return 0; }