KMP 字符串匹配算法详解

引言

KMP 算法是一种高效的字符串匹配算法，用于在文本串中查找模式串的位置。本文将详细讲解其原理、优化过程及 C++ 实现。

问题描述

给定两个字符串 A（文本串）和 B（模式串），输出字符串 B 在字符串 A 的每一个出现的位置。

数据规模： 设 |S| 表示字符串 S 的长度。 1 ≤ |A|, |B| ≤ 1.1 × 10^7

由于数据规模较大，必须考虑 O(|A| + |B|) 的算法。

暴力匹配分析

基础暴力

直接暴力匹配每一位，时间复杂度为 O(|A| * |B|)。

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

void bruteForceSearch(char text[], char pattern[]) {
    int n = strlen(text);
    int m = strlen(pattern);
    for (int i = 0; i <= n - m; i++) {
        int ok_pos = 0;
        for (int j = 0; j < m; j++) {
            if (text[i + j] == pattern[j]) {
                ok_pos++;
            }
        }
        if (ok_pos == m) {
            printf("%d\n", i);
        }
    }
}

简单优化

只要有一个位置不匹配，就立即跳出内层循环。虽然最坏情况仍是 O(|A| * |B|)，但在实际数据中往往能提升效率。

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

void optimizedBruteForce(char text[],  pattern[]) {
     n = (text);
     m = (pattern);
     ( i = ; i <= n - m; i++) {
         j = ;
         (; j < m; j++) {
             (text[i + j] != pattern[j]) {
                ;
            }
        }
         (j == m) {
            (, i + );
        }
    }
}