7-17 KMP模式匹配算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了7-17 KMP模式匹配算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

给定主串s和模式串p，编写程序使用KMP算法进行模式匹配，计算p在s中出现的首位置，若p不在s中则输出−1。字符串下标从0开始。

输入格式:

输入为2行，第1行为主串s，第2行为模式串p。主串和模式串长度不超过105。

输出格式:

输出为2行，第1行为3个整数，表示分别在模式串p的pm/4,p2m/4,p3m/4处失配后，模式串下一次匹配的位置（即next[j]或f[j−1]+1的值，j=m/4,2m/4,3m/4），每个整数后一个空格，m表示模式串p的长度；第2行为一个整数，表示p在s中出现的首位置，若p不在s中则输出−1。文章来源地址https://www.toymoban.com/news/detail-856443.html

输入样例:

qwerababcabcabcabcdaabcabhlk
abcabcabcabc

输出样例:

0 3 6 
6

参考代码

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

// 定义最大字符串长度
#define MAX_LEN 100000

// 计算模式串的next数组
void get_next(char *p, int *next, int m) {
    next[0] = -1; // 初始化next[0]为-1
    int i = 0; // 定义i指向当前字符
    int j = -1; // 定义j指向前缀的最后一个字符
    while (i < m - 1) { // 循环遍历模式串
        if (j == -1 || p[i] == p[j]) { // 如果j为-1或者当前字符与前缀的最后一个字符相等
            i++; // i向后移动一位
            j++; // j向后移动一位
            next[i] = j; // 设置next[i]为j
        } else { // 否则
            j = next[j]; // j回溯到next[j]的位置
        }
    }
}

// 使用KMP算法进行模式匹配，返回首次匹配的位置，若无匹配则返回-1
int kmp(char *s, char *p, int *next, int n, int m) {
    int i = 0; // 定义i指向主串的当前字符
    int j = 0; // 定义j指向模式串的当前字符
    while (i < n && j < m) { // 循环遍历主串和模式串
        if (j == -1 || s[i] == p[j]) { // 如果j为-1或者当前字符相等
            i++; // i向后移动一位
            j++; // j向后移动一位
        } else { // 否则
            j = next[j]; // j回溯到next[j]的位置
        }
    }
    if (j == m) { // 如果j达到模式串的末尾
        return i - j; // 返回匹配的首位置
    } else { // 否则
        return -1; // 返回-1表示无匹配
    }
}

int main() {
    char s[MAX_LEN + 1]; // 定义主串s
    char p[MAX_LEN + 1]; // 定义模式串p
    int next[MAX_LEN + 1]; // 定义next数组
    scanf("%s", s); // 输入主串s
    scanf("%s", p); // 输入模式串p
    int n = strlen(s); // 获取主串长度
    int m = strlen(p); // 获取模式串长度
    get_next(p, next, m); // 计算模式串的next数组
    // 输出next数组中的三个值
    printf("%d %d %d \n", next[m / 4], next[m / 2], next[m * 3 / 4]);
    // 输出模式匹配的结果
    printf("%d", kmp(s, p, next, n, m));
    return 0; // 结束程序
}

到了这里，关于7-17 KMP模式匹配算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！