【kmp算法】数据结构实验之串三：KMP应用

曾经终败给现在 2022-06-07 05:26 167阅读 0赞

Think:  
1知识点：kmp算法  
2题意：先输入n，然后输入n个数字，再输入m，然后再输入m个数字，询问这m个数是否为n个数字的唯一子区间\[l, r\]，若是，则存在子区间\[l, r\]则输出l, r，若不存在则输出-1  
3反思：  
（1）：区间\[l, r\]必须是唯一存在  
（2）：当第一次寻找到一个区间\[l, r\]之后再次寻找判断是否是唯一存在时，要注意再次寻找时的出发位置

[SDUT题目链接][SDUT]

以下为Wrong Answer代码——未判断区间\[l, r\]是否是唯一的

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int max_size = 1004014;
    
    int _next[max_size];
    int rec1[max_size], rec2[max_size];
    
    void get_next(int P[], int num_P);
    void kmp(int T[], int num_T, int P[], int num_P);
    
    int main(){
        int n, m, i;
        while(~scanf("%d", &n)){
            for(i = 0; i < n; i++)
                scanf("%d", &rec1[i]);
            scanf("%d", &m);
            for(i = 0; i < m; i++)
                scanf("%d", &rec2[i]);
            kmp(rec1, n, rec2, m);
        }
        return 0;
    }
    void get_next(int P[], int num_P){
        int q, k;
        _next[0] = 0;
        k = 0;
        for(q = 1; q < num_P; q++){
            while(k > 0 && P[q] != P[k]){
                k = _next[k-1];
            }
            if(P[q] == P[k])
                k++;
            _next[q] = k;
        }
        return;
    }
    void kmp(int T[], int num_T, int P[], int num_P){
        int k, i;
        get_next(P, num_P);
        k = 0;
        for(i = 0; i < num_T; i++){
            while(k > 0 && P[k] != T[i]){
                k = _next[k-1];
            }
            if(P[k] == T[i])
                k++;
            if(k == num_P){
                int id = i+1-num_P;
                printf("%d %d\n", id+1, i+1);
                return;
            }
        }
        printf("-1\n");
        return;
    }

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int max_size = 1004014;
    
    int _next[max_size];
    int rec1[max_size], rec2[max_size];
    
    void get_next(int P[], int num_P);
    void kmp(int T[], int num_T, int P[], int num_P);
    
    int main(){
        int n, m, i;
        while(~scanf("%d", &n)){
            for(i = 0; i < n; i++)
                scanf("%d", &rec1[i]);
            scanf("%d", &m);
            for(i = 0; i < m; i++)
                scanf("%d", &rec2[i]);
            kmp(rec1, n, rec2, m);
        }
        return 0;
    }
    void get_next(int P[], int num_P){
        int q, k;
        _next[0] = 0;
        k = 0;
        for(q = 1; q < num_P; q++){
            while(k > 0 && P[q] != P[k]){
                k = _next[k-1];
            }
            if(P[q] == P[k])
                k++;
            _next[q] = k;
        }
        return;
    }
    void kmp(int T[], int num_T, int P[], int num_P){
        int k, i, l, r, cnt = 0;
        get_next(P, num_P);
        k = 0;
        for(i = 0; i < num_T; i++){
            while(k > 0 && P[k] != T[i]){
                k = _next[k-1];
            }
            if(P[k] == T[i])
                k++;
            if(k == num_P){
                cnt++;
                if(cnt == 1){
                    l = i+1-num_P, r = i;
                }
                i = i+1-num_P;
                k = 0;
            }
        }
        if(cnt == 1) printf("%d %d\n", l+1, r+1);
        else printf("-1\n");
        return;
    }

[SDUT]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2226/pid/3311