C语言字符串中的高性能搜索算法

在C语言中，有几种高性能的字符串搜索算法，可以用于在一个较大的文本或字符串中查找子字符串

1. KMP算法（Knuth-Morris-Pratt算法）

KMP算法是一种线性时间复杂度的字符串搜索算法。它的优点是避免了在不匹配时重新检查之前已经匹配的字符。KMP算法的时间复杂度为O(n+m)，其中n是文本长度，m是模式串（子字符串）的长度。

void kmp_search(const char *text, const char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    int pi[m];

    // 构建部分匹配表
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern[j] != pattern[i]) {
            j = pi[j - 1];
        }
        if (pattern[j] == pattern[i]) {
            j++;
        }
        pi[i] = j;
    }

    // 搜索
    j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == m) {
            printf("Pattern found at index %d\n", i - m + 1);
            j = pi[j - 1];
        }
    }
}

2. Boyer-Moore算法

Boyer-Moore算法是一种从右到左的字符串搜索算法，它通过构建一个跳过表来跳过不可能的匹配。这使得算法在最坏情况下具有O(n/m)的时间复杂度。

void boyer_moore_search(const char *text, const char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    int skip[256];

    // 构建跳过表
    for (int i = 0; i < 256; i++) {
        skip[i] = m;
    }
    for (int i = 0; i < m - 1; i++) {
        skip[(int)pattern[i]] = m - i - 1;
    }

    // 搜索
    int i = m - 1;
    while (i < n) {
        int j = m - 1;
        while (j >= 0 && text[i] == pattern[j]) {
            i--;
            j--;
        }
        if (j < 0) {
            printf("Pattern found at index %d\n", i + 1);
            i += m;
        } else {
            i += skip[(int)text[i]];
        }
    }
}

3. Rabin-Karp算法

Rabin-Karp算法是一种基于哈希的字符串搜索算法。它通过计算模式串和文本子串的哈希值来比较它们。如果哈希值相等，则进行字符级别的比较。Rabin-Karp算法的平均时间复杂度为O(n+m)。

#include <stdbool.h>

// 哈希函数
unsigned long hash(const char *str, int len) {
    unsigned long h = 0;
    for (int i = 0; i < len; i++) {
        h = (h << 4) + str[i];
    }
    return h;
}

void rabin_karp_search(const char *text, const char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    unsigned long pattern_hash = hash(pattern, m);

    for (int i = 0; i <= n - m; i++) {
        unsigned long text_hash = hash(&text[i], m);
        if (pattern_hash == text_hash) {
            bool match = true;
            for (int j = 0; j < m; j++) {
                if (text[i + j] != pattern[j]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                printf("Pattern found at index %d\n", i);
            }
        }
    }
}

这些算法在实际应用中的性能取决于具体问题和数据集。在选择合适的算法时，请根据你的需求和数据特点进行权衡。