91超碰碰碰碰久久久久久综合_超碰av人澡人澡人澡人澡人掠_国产黄大片在线观看画质优化_txt小说免费全本

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

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

發布時間:2024-08-30 10:14:02 來源:億速云 閱讀:91 作者:小樊 欄目:編程語言

在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];
        }
    }
}
  1. 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]];
        }
    }
}
  1. 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);
            }
        }
    }
}

這些算法在實際應用中的性能取決于具體問題和數據集。在選擇合適的算法時,請根據你的需求和數據特點進行權衡。

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

顺义区| 巴彦县| 隆尧县| 徐州市| 莱芜市| 盘锦市| 星座| 桐梓县| 望江县| 峨山| 宜昌市| 安溪县| 赤城县| 齐河县| 于田县| 望奎县| 山丹县| 乌鲁木齐县| 榆林市| 富裕县| 汤原县| 深圳市| 江油市| 云安县| 怀集县| 金川县| 西畴县| 化州市| 鹤壁市| 闸北区| 沁源县| 石家庄市| 博乐市| 乐至县| 潜山县| 西盟| 梧州市| 通辽市| 荔波县| 临猗县| 宣恩县|