kmp算法

kmp算法C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 构建部分匹配表（next数组）
void computeLPSArray(const char *pattern, int pattern_len, int *lps) {int length = 0;  // 当前最长公共前后缀长度lps[0] = 0;     // 首字符无前缀，直接置0int i = 1;while (i < pattern_len) {if (pattern[i] == pattern[length]) {length++;lps[i] = length;i++;} else {if (length != 0) {// 回退到前一个最长匹配位置length = lps[length - 1];} else {// 无法进一步回退，当前lps为0lps[i] = 0;i++;}}}
}// KMP搜索算法
int KMPSearch(const char *text, const char *pattern) {int text_len = strlen(text);int pattern_len = strlen(pattern);if (pattern_len == 0) return 0;  // 空模式直接匹配int *lps = (int*)malloc(pattern_len * sizeof(int));computeLPSArray(pattern, pattern_len, lps);int i = 0;  // text索引int j = 0;  // pattern索引while (i < text_len) {if (pattern[j] == text[i]) {i++;j++;}// 找到完全匹配if (j == pattern_len) {free(lps);return i - j;  // 返回匹配起始位置}// 失配且j未到开头else if (i < text_len && pattern[j] != text[i]) {if (j != 0) {j = lps[j - 1];  // 根据lps表回退} else {i++;  // 无法回退，移动text指针}}}free(lps);return -1;  // 未找到匹配
}int main() {const char *text = "ABABDABACDABABCABAB";const char *pattern = "ABABCABAB";int result = KMPSearch(text, pattern);if (result != -1) {printf("Pattern found at index: %d\n", result);} else {printf("Pattern not found\n");}return 0;
}

代码说明：

1. 核心思想：

   • 通过预处理模式字符串生成部分匹配表（LPS数组），记录每个位置的最长公共前后缀长度

   • 匹配失败时利用LPS数组避免回溯主字符串

2. computeLPSArray函数：

   • 时间复杂度：O(M)，M为模式串长度

   • 使用双指针技术构建LPS数组

   • 处理三种情况：字符匹配、字符不匹配但有公共前缀、字符不匹配且无公共前缀

3. KMPSearch函数：

   • 时间复杂度：O(N)，N为主串长度

   • 双指针遍历主串和模式串

   • 通过LPS数组实现高效回退

4. 优势：

   • 相比暴力匹配的O(MN)时间复杂度，优化为O(M+N)

   • 适合处理大量重复模式串的场景

   • 特别适合流式数据匹配（不需要存储整个主串）

示例输出：

Pattern found at index: 10

可以通过修改main函数中的text和pattern变量来测试不同输入。算法正确处理以下情况：

• 模式串出现在开头/中间/末尾

• 存在多个候选匹配

• 模式串包含重复子串

• 完全失配的情况