解題報告 之 POJ1226 Substrings

解題報告 之 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;
}