程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 解題報告 之 POJ1226 Substrings

解題報告 之 POJ1226 Substrings

編輯:C++入門知識

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




  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved