官方接单发单平台上线!有接单发单需求的请直接发布需求,或注册接单!点击此处查看详情!

C语言暴力匹配、KMP和Sunday算法都是字符串的匹配算法

时间:2023-11-06 浏览:260 分类:C/C++程序代做

91代做网-专注各种程序代做

包括但不限于:各类毕设课设、作业辅导、代码答疑、报告论文、商业程序开发、论文复现和小程序开发等。

也欢迎各行业程序员加入我们,具体请联系客服详聊:QQ号:,微信号:,接单Q群:

C语言
任务描述
暴力匹配、KMP和Sunday算法都是字符串的匹配算法,任务是根据输入,输出指定匹配算法的字符比较次数
可以参考博客https://zhuanlan.zhihu.com/p/159879354
编程要求
根据提示,编写代码,计算并输出字符比较次数。
测试说明
平台会对你编写的代码进行测试:一行一个测试用例,用2个逗号分隔为三部分,第一部分是方法名称M,
Brute/KMP/Sunday,第二部分是主串S、第三部分是模式串T。你的任务是计算T在S中,用M方法匹配,需要多少次比较,并输出。
主串S和模式串T仅有ASCII大小写字母和数字组成。
测试输入:KMP,AAAAAAAAAA,BBBB;预期输出:7
测试输入:Brute,AAAAAAAAAA,BBBB;预期输出:7

#include <stdio.h>
#include <string.h>

// Brute算法
int brute_match(const char* s, const char* t) {
    int i = 0, j = 0, count = 0;
    while (s[i] != '\0' && t[j] != '\0') {
        count++;
        if (s[i] == t[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    return count;
}

// KMP算法
int kmp_match(const char* s, const char* t) {
    int i = 0, j = 0, count = 0;
    int next[strlen(t)];
    next[0] = -1;
    while (t[i + 1] != '\0') {
        if (j == -1 || t[i] == t[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    i = 0, j = 0;
    while (s[i] != '\0' && t[j] != '\0') {
        count++;
        if (j == -1 || s[i] == t[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    return count;
}

// Sunday算法
int sunday_match(const char* s, const char* t) {
    int i = 0, j = 0, k, count = 0;
    int pos[128] = {0};
    int len_t = strlen(t), len_s = strlen(s);
    for (i = 0; i < 128; i++) {
        pos[i] = -1;
    }
    for (i = 0; i < len_t; i++) {
        pos[t[i]] = i;
    }
    i = 0, j = 0;
    while (i <= len_s - len_t) {
        count++;
        for (k = 0; k < len_t; k++) {
            if (s[i + k] != t[k]) {
                i += len_t - pos[s[i + len_t]];
                break;
            }
        }
        if (k == len_t) {
            return count;
        }
    }
    return count;
}

int main() {
    char method[10], s[100], t[100];
    while (scanf("%[^,],%[^,],%s", method, s, t) != EOF) {
        int count = 0;
        if (strcmp(method, "Brute") == 0) {
            count = brute_match(s, t);
        } else if (strcmp(method, "KMP") == 0) {
            count = kmp_match(s, t);
        } else if (strcmp(method, "Sunday") == 0) {
            count = sunday_match(s, t);
        }
        printf("%d\n", count);
    }
    return 0;
}


客服