🔍 KMP算法动画演示

📝 C语言实现代码

// KMP算法完整实现
#include <stdio.h>
#include <string.h>

// 构建Next数组（失败函数）
void buildNext(char* pattern, int* next, int m) {
    int j = 0;
    next[0] = 0;  // 第一个字符的next值为0
    
    for (int i = 1; i < m; i++) {
        // 当不匹配时，回退到next[j-1]位置
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        
        // 如果匹配，j前进一位
        if (pattern[i] == pattern[j]) {
            j++;
        }
        
        next[i] = j;  // 记录最长相同前后缀长度
    }
}

// KMP搜索算法
int kmpSearch(char* text, char* pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    
    if (m == 0) return 0;
    if (m > n) return -1;
    
    // 构建Next数组
    int next[m];
    buildNext(pattern, next, m);
    
    int j = 0;  // 模式串指针
    
    // 遍历文本串
    for (int i = 0; i < n; i++) {
        // 不匹配时根据next数组回退
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }
        
        // 匹配则前进
        if (text[i] == pattern[j]) {
            j++;
        }
        
        // 完全匹配
        if (j == m) {
            return i - m + 1;  // 返回匹配位置
        }
    }
    
    return -1;  // 未找到
}

// 主函数示例
int main() {
    char text[] = "ABABCABABABCABAB";
    char pattern[] = "ABABCABAB";
    
    int pos = kmpSearch(text, pattern);
    
    if (pos != -1) {
        printf("模式串在位置 %d 找到\n", pos);
    } else {
        printf("未找到模式串\n");
    }
    
    return 0;
}

/*
 * 算法复杂度分析：
 * 时间复杂度：O(n + m)
 * 空间复杂度：O(m)
 * 
 * 其中 n 是文本串长度，m 是模式串长度
 * 相比朴素匹配的 O(nm)，KMP算法更高效
 */