题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1238

Substrings

2
3
ABCD
BCDFF
BRCD
2
rose
orchid

2
2

【题意】

在给定字符串中找到最长公共子串， 或者给定字符串子串的反串；

最多100字符串，最长100，直接枚举

求反串可以用 <algorithm>中的reverse函数 ；

【源代码】

#include <iostream>
#include <algorithm>
using namespace std;
string str[110]; 
int t;
int cmp(const string& a, const string& b){
	return a.length()<b.length();
}
int dfs(string now,string rev,int len){
	for(int i=1;i<t;i++){
		int sign=0;
		for(int j=0;j+len<=str[i].length();j++){
			string sub=str[i].substr(j,len); //返回从j 开始 长度为len的子串
			if(sub==now||sub==rev) 
			{
				sign=1;break; // 找到就继续找
			}
		}
		if(!sign)
			return 0; //否则直接退出
	}
	return len;
}
int main(){
	int n;
	cin>>n;

	while(n--){
		cin>>t;
		for(int i=0;i<t;i++)
			cin>>str[i];
		sort(str,str+t,cmp);
		int len=str[0].length();
		int max=0;
		for(int i=len;i>=1;i--){
			for(int j=0;j+i<=len;j++){
				string now=str[0].substr(j,i);
				string rev=now;
				reverse(rev.begin(),rev.end());
				//for(int k=now.length()-1;k>=0;k--) //原先手写的翻转字符串，用了上一行的reverse 速度从 140ms 下降到109ms
				//	rev+=now[k];
				//cout<<rev<<endl;
				int ma=dfs(now,rev,i);
				if(ma>max)
					max=ma;
			}
		}
		cout<<max<<endl;
	}
	return 0;
}

hdu 1238 Substrings （暴搜，枚举）

原文：http://blog.csdn.net/chaiwenjun000/article/details/47335407