首页 > 代码库 > poj3080解题报告（暴力、最大公共子串）

poj3080解题报告（暴力、最大公共子串）

2024-07-06 22:43:02   217人阅读

 

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的所有子串中，找出字典排序在前的。（暴力~）

代码：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//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;
}

 

 

 


联系
我们