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

在C語言中，有幾種高性能的字符串搜索算法，可以用于在一個較大的文本或字符串中查找子字符串

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

KMP算法是一種線性時間復(fù)雜度的字符串搜索算法。它的優(yōu)點(diǎn)是避免了在不匹配時重新檢查之前已經(jīng)匹配的字符。KMP算法的時間復(fù)雜度為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];

    // 構(gòu)建部分匹配表
    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算法是一種從右到左的字符串搜索算法，它通過構(gòu)建一個跳過表來跳過不可能的匹配。這使得算法在最壞情況下具有O(n/m)的時間復(fù)雜度。

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

    // 構(gòu)建跳過表
    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算法是一種基于哈希的字符串搜索算法。它通過計(jì)算模式串和文本子串的哈希值來比較它們。如果哈希值相等，則進(jìn)行字符級別的比較。Rabin-Karp算法的平均時間復(fù)雜度為O(n+m)。

#include <stdbool.h>

// 哈希函數(shù)
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);
            }
        }
    }
}

這些算法在實(shí)際應(yīng)用中的性能取決于具體問題和數(shù)據(jù)集。在選擇合適的算法時，請根據(jù)你的需求和數(shù)據(jù)特點(diǎn)進(jìn)行權(quán)衡。