KMP算法的初级扩展应用

客官°小女子只卖身不卖艺 2022-07-12 01:23 127阅读 0赞

[sdut原题链接][sdut]  
bLue的文件查找器  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
bLue 的电脑里存了各种各样的文件，随着文件越来越多，查找文件也成了一个麻烦事。  
现在，他想要查找所有指定格式（扩展名）的文件，不过他并不会使用文件管理器自带的搜索功能，所以他想求你写一个文件查找器，来帮他查找所有指定格式的文件。

Input  
输入数据有多组（数据组数不超过 100），到 EOF 结束。  
对于每组数据：  
第一行输入一个整数 n (1 <= n <= 100) 和一个长度不超过 5 的字符串 ex，分别表示文件夹内的文件数量和要查找的文件的扩展名。  
接下来的 n 行，每行输入一个完整文件名。保证文件名不包含空格且长度不超过 100。

Output  
对于每组数据，按照输入顺序输出文件夹内所有扩展名符合查找要求的文件名。

Example Input  
6 cpp  
3717.cpp  
xunhuansai\_daima.zip  
xunhuansai\_jietibaogao.pdf  
C.cpp  
bLue.jpg  
cyk\_de\_richang.mp4

Example Output  
3717.cpp  
C.cpp

Hint  
1 文件名后缀前面应该有符号“.”（不带括号）  
2  
Example Input  
2 cpp  
3717.ccpp  
3717.cpp

Example Output  
3717.cpp

Author  
「2016年第六届ACM趣味编程循环赛 Round \#2」bLue

以下为accepted代码

#include <stdio.h>
    #include <string.h>
    #define MAXN 140
    char s[MAXN], p[9];
    int next[9];
    void get_next(char *p)
    {
        next[0] = -1;///初始化
        int i = 0, j = -1;
        int len = strlen(p);
        while(i < len-1)
        {
            if(j == -1 || p[i] == p[j])
            {
                i++;
                j++;
                next[i] = j;
            }
            else
                j = next[j];//失配回溯
        }
    }
    int kmp(char *s, char *p)
    {
        get_next(p);
        int len1 = strlen(s);
        int len2 = strlen(p);
        int i = len1-len2, j = 0;///灵活沟通配对起始位置（）
        ///可以通过i的初始值灵活沟通配对起始位置，可以通过len1的值灵活沟通配对终点位置
        if(s[i-1] != '.')
            return -1;
        while(i < len1 && j < len2)
        {
            if(j == -1 || s[i] == p[j])
            {
                i++;
                j++;
            }
            else
                j = next[j];//失配回溯
        }
        if(j == len2)
            return 1;
        else
            return -1;
    }
    int main()
    {
        int n;
        while(scanf("%d %s", &n, p) != EOF)
        {
            while(n--)
            {
                scanf("%s", s);
                if(kmp(s, p) == 1)
                    printf("%s\n", s);
            }
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 4ms
    Take Memory: 108KB
    Submit time: 2017-02-06 21:14:04
    ****************************************************/

以下为wrong answer代码

#include <stdio.h>
    #include <string.h>
    #define MAXN 140
    char s[MAXN], p[9];
    int next[9];
    void get_next(char *p)
    {
        next[0] = -1;///初始化
        int i = 0, j = -1;
        int len = strlen(p);
        while(i < len-1)
        {
            if(j == -1 || p[i] == p[j])
            {
                i++;
                j++;
                next[i] = j;
            }
            else
                j = next[j];//失配回溯
        }
    }
    int kmp(char *s, char *p)
    {
        get_next(p);
        int len1 = strlen(s);
        int len2 = strlen(p);
        int i = len1-len2, j = 0;///灵活沟通配对起始位置（）
        ///可以通过i的初始值灵活沟通配对起始位置，可以通过len1的值灵活沟通配对终点位置
        while(i < len1 && j < len2)
        {
            if(j == -1 || s[i] == p[j])
            {
                i++;
                j++;
            }
            else
                j = next[j];//失配回溯
        }
        if(j == len2)
            return 1;
        else
            return -1;
    }
    int main()
    {
        int n;
        while(scanf("%d %s", &n, p) != EOF)
        {
            while(n--)
            {
                scanf("%s", s);
                if(kmp(s, p) == 1)
                    printf("%s\n", s);
            }
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Wrong Answer
    Take time: 4ms
    Take Memory: 108KB
    Submit time: 2017-02-06 21:10:04
    ****************************************************/

wrong answer cause:  
1 文件的扩展名的格式要求

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2002/pid/3717