C语言实现KMP字符串匹配算法

简介

在字符串处理中，字符串匹配是一项常见的任务。KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，它能够在不进行回溯的情况下快速找到模式串在主串中出现的位置。相较于传统的暴力匹配算法，KMP算法通过预处理模式串，构建部分匹配表（也称为前缀函数），从而大大提高了匹配效率。本文将详细介绍如何使用C语言实现KMP字符串匹配算法。

目录

1. 基础概念
   • 部分匹配表（前缀函数）
   • KMP算法原理
2. 使用方法
   • 构建部分匹配表
   • 字符串匹配过程
3. 常见实践
   • 查找字符串中所有匹配位置
   • 处理长字符串匹配
4. 最佳实践
   • 优化部分匹配表的构建
   • 错误处理与边界条件
5. 代码示例
6. 小结
7. 参考资料

基础概念

部分匹配表（前缀函数）

部分匹配表（Partial Match Table），也称为前缀函数（Prefix Function），是KMP算法的核心。它记录了模式串中每个位置之前的子串的最长相等前缀和后缀的长度。例如，对于模式串 “ABABAC”，其部分匹配表为 [0, 0, 1, 2, 3, 0]。

KMP算法原理

KMP算法的核心思想是利用已经匹配的部分信息，避免不必要的重复比较。当在主串和模式串的匹配过程中出现不匹配时，根据部分匹配表，直接将模式串向右移动一定的距离，而不是从头开始重新匹配。

使用方法

构建部分匹配表

构建部分匹配表的过程如下：

1. 初始化部分匹配表，长度与模式串相同，初始值都为0。
2. 遍历模式串，对于每个位置i，计算其最长相等前缀和后缀的长度。
3. 如果模式串的第i个字符与前缀的下一个字符相同，则部分匹配表的值加1。
4. 如果不相同，则回溯到前缀的前一个位置，继续比较。

以下是构建部分匹配表的C语言代码：

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

void computeLPSArray(char *pat, int M, int *lps) {
    int len = 0;
    lps[0] = 0; // lps[0] 总是 0

    int i = 1;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len!= 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

字符串匹配过程

字符串匹配的过程如下：

1. 初始化主串和模式串的索引。
2. 遍历主串，比较主串和模式串的字符。
3. 如果字符相同，则继续比较下一个字符。
4. 如果字符不同，则根据部分匹配表移动模式串。
5. 如果模式串完全匹配，则返回匹配的位置。

以下是字符串匹配的C语言代码：

int KMPSearch(char *txt, char *pat) {
    int M = strlen(pat);
    int N = strlen(txt);

    int lps[M];

    computeLPSArray(pat, M, lps);

    int i = 0; // 主串索引
    int j = 0; // 模式串索引
    while (i < N) {
        if (pat[j] == txt[i]) {
            i++;
            j++;
        }

        if (j == M) {
            return i - j;
        } else if (i < N && pat[j]!= txt[i]) {
            if (j!= 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;
}

常见实践

查找字符串中所有匹配位置

要查找字符串中所有匹配位置，可以在每次找到一个匹配后，继续在主串中查找下一个匹配。

void findAllMatches(char *txt, char *pat) {
    int M = strlen(pat);
    int N = strlen(txt);

    int lps[M];

    computeLPSArray(pat, M, lps);

    int i = 0; // 主串索引
    int j = 0; // 模式串索引
    while (i < N) {
        if (pat[j] == txt[i]) {
            i++;
            j++;
        }

        if (j == M) {
            printf("Pattern found at index %d\n", i - j);
            j = lps[j - 1];
        } else if (i < N && pat[j]!= txt[i]) {
            if (j!= 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

处理长字符串匹配

对于长字符串匹配，可以考虑分块处理，以减少内存占用。另外，在构建部分匹配表时，可以使用更高效的数据结构或算法来优化性能。

最佳实践

优化部分匹配表的构建

在构建部分匹配表时，可以进一步优化回溯过程，减少不必要的比较。例如，可以在构建部分匹配表时同时处理一些特殊情况，避免在匹配过程中重复处理。

错误处理与边界条件

在实现KMP算法时，要注意处理边界条件，如空字符串、模式串长度大于主串长度等情况。同时，要进行适当的错误处理，确保程序的稳定性。

代码示例

完整的C语言代码示例：

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

void computeLPSArray(char *pat, int M, int *lps) {
    int len = 0;
    lps[0] = 0; // lps[0] 总是 0

    int i = 1;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len!= 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int KMPSearch(char *txt, char *pat) {
    int M = strlen(pat);
    int N = strlen(txt);

    int lps[M];

    computeLPSArray(pat, M, lps);

    int i = 0; // 主串索引
    int j = 0; // 模式串索引
    while (i < N) {
        if (pat[j] == txt[i]) {
            i++;
            j++;
        }

        if (j == M) {
            return i - j;
        } else if (i < N && pat[j]!= txt[i]) {
            if (j!= 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;
}

void findAllMatches(char *txt, char *pat) {
    int M = strlen(pat);
    int N = strlen(txt);

    int lps[M];

    computeLPSArray(pat, M, lps);

    int i = 0; // 主串索引
    int j = 0; // 模式串索引
    while (i < N) {
        if (pat[j] == txt[i]) {
            i++;
            j++;
        }

        if (j == M) {
            printf("Pattern found at index %d\n", i - j);
            j = lps[j - 1];
        } else if (i < N && pat[j]!= txt[i]) {
            if (j!= 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

int main() {
    char txt[] = "ABABDABACDABABCABAB";
    char pat[] = "ABABCABAB";

    int result = KMPSearch(txt, pat);
    if (result == -1) {
        printf("Pattern not found\n");
    } else {
        printf("Pattern found at index %d\n", result);
    }

    printf("Finding all matches:\n");
    findAllMatches(txt, pat);

    return 0;
}

小结

KMP算法是一种高效的字符串匹配算法，通过构建部分匹配表，避免了不必要的回溯，大大提高了匹配效率。本文详细介绍了KMP算法的基础概念、使用方法、常见实践和最佳实践，并给出了完整的C语言代码示例。希望读者通过本文的学习，能够深入理解并熟练使用KMP算法进行字符串匹配。

参考资料

• 《算法导论》（Introduction to Algorithms）
• Wikipedia - Knuth-Morris-Pratt algorithm