POJ 3080 Blue Jeans (KMP)

Posted on | In | 阅读

枚举第一个串的长度和起始点，然后用KMP去一个个比较，得到最后一个能匹配的长度，同时要替换字典序最大的那个串

C++ Code

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>

using namespace std;

char dna[12][65];
int nex[65];

void getNext(char *p, int len){
    nex[0] = -1;
    int i = 0, j = -1;
    while(i < len){
        if(j == -1 || p[i] == p[j]){
            i++;
            j++;
            nex[i] = j;
        }else{
            j = nex[j];
        }
    }
}

bool kmp(char *a, char*b, int len1, int len2){
    int i = 0, j = 0;
    while(i < len1){
        if(j == -1 || a[i] == b[j]){
            i++;
            j++;
        }else{
            j = nex[j];
        }
        if(j == len2){
            return true;
        }
    }
    return false;
}

int main(){
    int ca, num;
    scanf("%d", &ca);
    while(ca--){
        scanf("%d", &num);
        for(int i = 0; i < num; i++){
            scanf("%s", dna[i]);
        }
        char tmp[65];
        char tmp2[65];
        int final_len = 0;
        bool flag1, flag2;
        int pos;
        for(int len = 1; len <= 60; len++){
            flag2 = false;
            for(int i = 0; i <= 60-len; i++){
                strncpy(tmp, dna[0]+i, len);
                tmp[len] = '\0';
                getNext(tmp, len);
                flag1 = true;
                pos = -1;
                for(int j = 1; j < num; j++){
                    if(kmp(dna[j], tmp, 60, len) == false){
                        flag1 = false;
                        break;
                    }
                }
                if(flag1 == true){
                    final_len = len;
                    if(pos == -1 || strcmp(tmp, tmp2) > 0){
                        pos = i;
                        strncpy(tmp2, tmp, len);
                        tmp2[len] = '\0';
                        // printf("tmp2 %s\n", tmp2);
                    }
                    flag2 = true;
                }
            }
            if(flag2 == false)
                break;
        }
        if(final_len < 3)
            printf("no significant commonalities\n");
        else
            printf("%s\n", tmp2);
    }
    return 0;
}