顺序字符串朴素和kmp模式匹配c语言

顺序串匹配（Sequential Search）是一种简单直接的算法，也称为朴素搜索。当你需要在一个较长的文本串中查找一个给定的小串时，从头开始逐个字符比较，直到找到匹配或者遍历完整个文本。这种方法的时间复杂度是O(nm)，其中n是主串长度，m是模式串长度。

KMP（Knuth-Morris-Pratt）算法是一种改进后的模式匹配算法，它通过预处理模式串创建一个部分匹配表（Partial Match Table，简称PMT），用于跳过不需要比较的字符，当遇到不匹配的情况时，可以根据PMT直接定位到下一个应该开始比较的位置，大大减少了无效的比较。KMP算法的时间复杂度通常为O(m + n)。

以下是KMP算法的基本步骤在C语言中的实现：

1. 创建PMT：计算每个位置i的最长前缀和后缀公共部分的长度，存入数组next[]。
2. 主循环：对于主串中的每一个字符，如果和模式串中的当前字符相等，继续向后移动；如果不等，根据next[i]更新模式串的起始位置i。
3. 如果模式串遍历完，说明找到了匹配；如果主串也遍历完还没找到匹配，说明没有匹配。

#include <stdio.h>
int next[256]; // PMT

// 计算next数组
void computeNext(char* pattern) {
    int len = strlen(pattern);
    int j = -1;
    for (int i = 0; i < len; ++i) {
        while (j != -1 && pattern[j + 1] != pattern[i]) {
            j = next[j];
        }
        if (pattern[j + 1] == pattern[i]) {
            j++;
        }
        next[i] = j;
    }
}

// KMP匹配函数
bool kmpMatch(char* text, char* pattern) {
    int text_len = strlen(text), pat_len = strlen(pattern);
    computeNext(pattern);

    int i = 0, j = 0;
    while (i < text_len && j < pat_len) {
        if (text[i] == pattern[j]) {
            i++, j++;
        } else {
            if (j != 0)
                j = next[j - 1];
            else
                i++;
        }
    }
    return j == pat_len; // 如果j等于模式串长度，则匹配成功
}

int main() {
    // 使用KMP算法匹配...
}