C++字符串查找優化策略

在C++中，字符串查找是一個常見的操作。為了提高查找效率，可以采用一些優化策略。以下是一些建議：

1. 使用std::string::find函數：C++標準庫提供了std::string::find函數，用于查找子字符串在原字符串中的位置。這個函數已經經過了優化，可以滿足大部分情況下的字符串查找需求。

#include <iostream>
#include <string>

int main() {
    std::string str = "Hello, world!";
    std::string sub = "world";

    size_t pos = str.find(sub);
    if (pos != std::string::npos) {
        std::cout << "Substring found at position: " << pos << std::endl;
    } else {
        std::cout << "Substring not found" << std::endl;
    }

    return 0;
}

2. KMP算法：KMP（Knuth-Morris-Pratt）算法是一種高效的字符串查找算法，它可以在O(n+m)的時間復雜度內完成查找，其中n是原字符串的長度，m是子字符串的長度。KMP算法的核心在于預處理子字符串，構建一個部分匹配表（Partial Match Table），用于在查找過程中跳過不必要的比較。

#include <iostream>
#include <vector>
#include <string>

std::vector<int> build_partial_match_table(const std::string& sub) {
    int table_size = sub.length();
    std::vector<int> table(table_size, 0);
    int j = 0;

    for (int i = 1; i < table_size; ++i) {
        while (j > 0 && sub[i] != sub[j]) {
            j = table[j - 1];
        }
        if (sub[i] == sub[j]) {
            ++j;
        }
        table[i] = j;
    }

    return table;
}

size_t kmp_search(const std::string& str, const std::string& sub) {
    std::vector<int> table = build_partial_match_table(sub);
    int n = str.length();
    int m = sub.length();
    int j = 0;

    for (int i = 0; i < n; ++i) {
        while (j > 0 && str[i] != sub[j]) {
            j = table[j - 1];
        }
        if (str[i] == sub[j]) {
            ++j;
        }
        if (j == m) {
            return i - m + 1;
        }
    }

    return std::string::npos;
}

int main() {
    std::string str = "Hello, world!";
    std::string sub = "world";

    size_t pos = kmp_search(str, sub);
    if (pos != std::string::npos) {
        std::cout << "Substring found at position: " << pos << std::endl;
    } else {
        std::cout << "Substring not found" << std::endl;
    }

    return 0;
}

3. Boyer-Moore算法：Boyer-Moore算法是一種高效的字符串查找算法，它可以在O(n+m)的時間復雜度內完成查找，其中n是原字符串的長度，m是子字符串的長度。Boyer-Moore算法的核心在于預處理子字符串，構建一個壞字符表（Bad Character Table）和一個好后綴表（Good Suffix Table），用于在查找過程中跳過不必要的比較。

#include <iostream>
#include <vector>
#include <string>

std::vector<int> build_bad_character_table(const std::string& sub) {
    int table_size = 256;
    std::vector<int> table(table_size, sub.length());

    for (int i = 0; i < sub.length() - 1; ++i) {
        table[sub[i]] = i + 1;
    }

    return table;
}

std::vector<int> build_good_suffix_table(const std::string& str, const std::string& sub) {
    int str_length = str.length();
    int sub_length = sub.length();
    std::vector<int> table(sub_length, 0);
    int last_occurrence = sub_length;

    for (int i = str_length - 1; i >= 0; --i) {
        if (str[i] == sub[sub_length - 1]) {
            table[sub_length - 1] = i + 1;
            last_occurrence = sub_length;
        } else {
            table[sub[i]] = last_occurrence - 1;
        }
    }

    for (int i = sub_length - 2; i >= 0; --i) {
        table[sub[i]] = std::max(table[sub[i]], table[sub[i + 1]]);
    }

    return table;
}

size_t boyer_moore_search(const std::string& str, const std::string& sub) {
    std::vector<int> bad_character_table = build_bad_character_table(sub);
    std::vector<int> good_suffix_table = build_good_suffix_table(str, sub);
    int n = str.length();
    int m = sub.length();
    int i = 0;

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

        while (j >= 0 && str[i + j] == sub[j]) {
            --j;
        }

        if (j < 0) {
            return i;
        } else {
            i += std::max(bad_character_table[str[i + j]], good_suffix_table[j]);
        }
    }

    return std::string::npos;
}

int main() {
    std::string str = "Hello, world!";
    std::string sub = "world";

    size_t pos = boyer_moore_search(str, sub);
    if (pos != std::string::npos) {
        std::cout << "Substring found at position: " << pos << std::endl;
    } else {
        std::cout << "Substring not found" << std::endl;
    }

    return 0;
}

根據具體需求和場景，可以選擇合適的字符串查找算法進行優化。