1、什么是字符串匹配问题

字符串匹配问题是指在一个主串中查找一个模式串的出现位置或判断模式串是否在主串中存在的问题。在实际应用中，字符串匹配是一种常见的操作，例如在文本编辑器中查找关键字、在数据库中进行模糊查询、在网络数据传输中的数据包过滤等场景。

具体而言，字符串匹配问题通常涉及两个字符串：主串（main string）和模式串（pattern string）。主串是待搜索的字符串，而模式串是要在主串中查找的目标字符串。任务是找出模式串在主串中的所有出现位置或判断是否存在匹配。

字符串匹配问题的难点在于，搜索过程中需要高效地处理字符的比较和移动，特别是在主串和模式串较长的情况下。因此，有多种算法被设计用于解决字符串匹配问题，其中包括暴力匹配法、KMP 算法、Boyer-Moore 算法等。这些算法具有不同的时间复杂度和适用场景，可根据具体情况选择合适的算法。

2、暴力匹配法（Brute Force）

这是最简单直接的方法，即逐一比较主串和模式串的每一个字符，如果不匹配，则将模式串向右移动一位，直到找到匹配或者遍历完整个主串。时间复杂度为O((n-m+1)m)，其中n为主串长度，m为模式串长度。

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

int bruteForce(char *mainStr, char *pattern) {
    int n = strlen(mainStr);
    int m = strlen(pattern);

    for (int i = 0; i <= n - m; ++i) {
        int j;
        for (j = 0; j < m; ++j) {
            if (mainStr[i + j] != pattern[j]) {
                break;
            }
        }
        if (j == m) {
            return i; // 匹配成功，返回匹配位置
        }
    }

    return -1; // 未匹配成功
}

int main() {
    char mainStr[] = "Hello, World!";
    char pattern[] = "World";

    int result = bruteForce(mainStr, pattern);

    if (result != -1) {
        printf("Pattern found at position: %d\n", result);
    } else {
        printf("Pattern not found.\n");
    }

    return 0;
}

匹配结果：

2、KMP 算法解决字符串匹配

KMP 算法通过计算模式串的最长前缀和最长后缀的匹配长度，实现在匹配失败时，快速移动模式串的位置。时间复杂度为O(n+m)，其中n为主串长度，m为模式串长度。

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

void computeLPSArray(char *pattern, int m, int *lps) {
    int len = 0;
    int i = 1;
    lps[0] = 0;

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

int KMP(char *mainStr, char *pattern) {
    int n = strlen(mainStr);
    int m = strlen(pattern);

    int *lps = (int *)malloc(sizeof(int) * m);
    computeLPSArray(pattern, m, lps);

    int i = 0; // 主串指针
    int j = 0; // 模式串指针

    while (i < n) {
        if (pattern[j] == mainStr[i]) {
            i++;
            j++;
        }

        if (j == m) {
            free(lps);
            return i - j; // 匹配成功，返回匹配位置
        } else if (i < n && pattern[j] != mainStr[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }

    free(lps);
    return -1; // 未匹配成功
}

int main() {
    char mainStr[] = "Hello, World!";
    char pattern[] = "World";

    int result = KMP(mainStr, pattern);

    if (result != -1) {
        printf("Pattern found at position: %d\n", result);
    } else {
        printf("Pattern not found.\n");
    }

    return 0;
}

算法结果：

3、Boyer-Moore 算法

Boyer-Moore 算法通过预处理模式串和启发函数，实现在匹配失败时，快速移动模式串的位置。时间复杂度为O(n+m)，其中n为主串长度，m为模式串长度。

// Boyer-Moore 字符串匹配算法 - 只采用一维坏字符表
// https://writings.sh/post/algorithm-string-searching-boyer-moore

#include <assert.h>
#include <stdio.h>   // for printf
#include <string.h>  // for strlen, strncmp

// 字符集大小
#define S 256

#define max(a, b) ((a < b) ? b : a)

// ComputeBadCharTable 计算一维坏字符表
void ComputeBadCharTable(char *p, int m, int table[]) {
    // 初始化每一个字符的坏字符表值为 m
    for (int i = 0; i < S; i++) {
        table[i] = m;
    }
    // 对尾巴左边的字符，不断覆盖它到尾巴 last 的距离
    // 此处采用 i < last 而非 i <= last 是因为尾巴字符到本身的距离是 0
    // 坏字符的对齐目标绝不在尾巴字符上。
    int last = m - 1;
    for (int i = 0; i < last; i++) {
        char ch = p[i];
        table[ch] = last - i;
    }
}

// BoyerMoore 从长度为 n 的字符串 s 中查找长度为 m 的字符串 p ， 返回其位置.
// 找不到则返回 -1
// 只采用一维坏字符表的方式
int BoyerMoore(char *s, int n, char *p, int m) {
    int bad_char_table[S];

    ComputeBadCharTable(p, m, bad_char_table);

    // 初始化，i, j 右对齐
    int i = m - 1;

    while (i < n) {
        int j = m - 1;

        // 自右向左匹配
        while (j >= 0 && p[j] == s[i]) {
            j--;
            i--;
        }

        if (j < 0) {
            // 命中, 返回起始位置
            return i + 1;
        }

        // 失配时，跳转的多少
        // 如果只是采用 i = bad_char_table[s[i]] 的话，会有可能发生匹配回溯
        // 我们要至少子串右移对齐一位，即主串迭代至少 m-j 才行
        i += max(bad_char_table[s[i]], m - j);
    }

    return -1;
}

int main(void) {
    char *s = "ABCDABEABDCBCDDBBCDBACD";
    char *p1 = "BCDBACD";
    char *p2 = "BCDDBB";
    char *p3 = "EABDCB";
    char *p4 = "BBCDBD";
    char *p5 = "DDBBCD";

    char *s1 = "BBBBBBBBBBBBBBBBBBBBBABBBBB";
    char *p6 = "ABBBBB";

    assert(BoyerMoore(s, strlen(s), p1, strlen(p1)) == 16);
    assert(BoyerMoore(s, strlen(s), p2, strlen(p2)) == 11);
    assert(BoyerMoore(s, strlen(s), p3, strlen(p2)) == 6);
    assert(BoyerMoore(s, strlen(s), p4, strlen(p4)) == -1);
    assert(BoyerMoore(s, strlen(s), p5, strlen(p5)) == 13);
    assert(BoyerMoore(s1, strlen(s1), p6, strlen(p6)) == 21);
    return 0;
}

4、总结

以上提供了三种常见的字符串匹配算法的实现示例，包括暴力匹配法（Brute Force）、KMP 算法和Boyer-Moore 算法。你可以根据需要选择其中一种算法进行使用。

在使用这些算法时，需要注意以下几点：

• 暴力匹配法： 简单直接，适用于小规模的字符串匹配，但在大规模数据下性能较差。
• KMP 算法： 对于较长的模式串和主串，性能相对较好，适用于大规模数据。
• Boyer-Moore 算法： 在实践中通常比 KMP 算法性能更好，尤其是在模式串较短的情况下。适用于大规模数据。

在实际应用中，选择合适的算法取决于具体的需求和数据规模。如果是小规模数据，简单的暴力匹配可能已经足够，但对于大规模数据，考虑使用更高效的算法。