本文主要是介绍poj3080解题报告（暴力、最大公共子串），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
POJ 3080，题目链接http://poj.org/problem?id=3080
题意：
就是求m个长度为60的字符串的最长连续公共子串，2<=m<=10
规定：
1、最长公共串长度小于3输出no significant commonalities
2、若出现多个等长的最长的子串，则输出字典序最小的串
思路：
1. 求公共最小连续子串，那么先把第一个串长度>=3的所有连续子串找出来，然后由短到长查看所有主串是否有该子串。
2. 如果发现一个公共子串，那么就开始找长度+1的公共子串；如果指定长度的所有子串都找不出一条是共有的，那么-1长度就是最长的公共子串。
例：长度为3的子串匹配时，当发现第一个长度为3的公共子串，则开始找长度为4的子串，如果发现第一个长度为4的子串，则开始找长度为5的子串，如果没有找到长度为5的公共子串，那么他们的最长公共子串长度就为4，此时就在长度为4的所有子串中，找出字典排序在前的。（暴力~）
代码：
//680K 32MS
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
using std::string;
using std::vector;
#define DNA_Len 60
bool BMSearch(const char* s, const char* t)
{
const char *p = strstr(s, t);
if (p) return true;
else return false;
}
int main()
{
char temp[DNA_Len+1];
vector<string> subStr[DNA_Len+1]; // 3-60
int caseNum;
scanf("%d",&caseNum);
while (caseNum-- > 0)
{
int deqNum;//2 <= m <= 10
scanf("%d", &deqNum);
char **p = new char*[deqNum];
for (int i=0; i<deqNum; ++i)
{
p[i] = new char[DNA_Len+1];
memset(p[i], 0, DNA_Len+1);
scanf("%s", p[i]);
}
//1. 获取第一个串中 长度为3-60的所有子串 （小于3的输出no significant commonalities）
for (int len=3; len<=60; ++len){
subStr[len].clear();
for (int i=0; i<=60-len; ++i){
strncpy(&temp[0], p[0]+i, len);
temp[len] = 0;
subStr[len].push_back(temp);
}
}
//2. 子串由少到多 再deqNum个主串中查找， 如果都有该子串 则保存后查找下一个长度的子串，直到找不到
memset(temp, 0, DNA_Len+1);
bool hasOneNotGot; //标记 deqNum个主串中，如果有一个没有找到那么就为true
for (int subStrLen=3; subStrLen<=60; ++subStrLen){
for (int subNum=0,count=subStr[subStrLen].size(); subNum<count; ++subNum){
hasOneNotGot = false;
for (int strIdx=0 ; strIdx<deqNum; ++strIdx){
if (! BMSearch(p[strIdx], subStr[subStrLen].at(subNum).c_str())){
hasOneNotGot = true;
break;
}
}
if (! hasOneNotGot) { //找到了就退出，找下一个长度的串,没找到就继续
strcpy(temp, subStr[subStrLen].at(subNum).c_str());
break;
}
}
if (hasOneNotGot){ //该长度的子串没有找到 那么temp是最长的子串 或temp为空
break;
}
}
if (strlen(temp) >= 3){
//多个最长子串 按照字典排序
int len = strlen(temp);
vector<string> multiString;
bool searched;
for (int i=0,count=subStr[len].size(); i<count; ++i)
{
searched = true;
for (int strIdx=0 ; strIdx<deqNum; ++strIdx){
if (! BMSearch(p[strIdx], subStr[len].at(i).c_str())){
searched = false;
break;
}
}
if (searched) multiString.push_back(subStr[len].at(i));
}
strcpy(temp, multiString.at(0).c_str());
for (int i=1,count=multiString.size(); i<count; ++i)
{
if (strcmp(temp, multiString.at(i).c_str()) > 0){
strcpy(temp, multiString.at(i).c_str());
}
}
printf("%s\n", temp);
}
else {
printf("no significant commonalities\n");
}
for (int i=0; i<deqNum; ++i) delete [](p[i]);
delete []p;
}
return 0;
}
这篇关于poj3080解题报告（暴力、最大公共子串）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
