面试题：C++ STL find模糊查找的性能优化

优化思路

数据结构优化
- Trie树：将子串集合构建成Trie树。Trie树可以高效地存储和检索字符串集合，通过共享前缀减少存储空间，并在查找时能够快速排除不匹配的分支。例如，对于子串 "apple", "app", "banana"，Trie树可以在公共前缀 "app" 处共享节点。
- 哈希表：使用哈希表存储子串集合。哈希表可以在O(1) 的平均时间复杂度内判断一个子串是否存在。对于模糊查找，可以将每个子串的哈希值预先计算并存储在哈希表中，在查找时计算长字符串中每个可能子串的哈希值并进行比对。但要注意哈希冲突的处理。
查找算法优化
- 滑动窗口：对于长字符串，采用滑动窗口的方式进行查找。窗口大小从最短子串长度到最长子串长度变化，在窗口移动过程中，计算窗口内子串的哈希值（如果使用哈希表优化）或者在Trie树中进行匹配。这样可以避免对每个字符位置都进行全量子串的查找，减少不必要的计算。
- 多线程：如果硬件支持，可以利用多线程技术并行处理长字符串的不同部分。例如，将长字符串划分为多个部分，每个线程负责在自己的部分中查找子串集合，最后汇总结果。

关键代码示例

Trie树构建与查找

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

const int ALPHABET_SIZE = 26;

// Trie节点结构
struct TrieNode {
    TrieNode* children[ALPHABET_SIZE];
    bool isEndOfWord;

    TrieNode() {
        for (int i = 0; i < ALPHABET_SIZE; ++i) {
            children[i] = nullptr;
        }
        isEndOfWord = false;
    }
};

// 插入子串到Trie树
void insert(TrieNode* root, const std::string& word) {
    TrieNode* node = root;
    for (char c : word) {
        int index = c - 'a';
        if (!node->children[index]) {
            node->children[index] = new TrieNode();
        }
        node = node->children[index];
    }
    node->isEndOfWord = true;
}

// 在Trie树中查找子串
bool search(TrieNode* root, const std::string& word) {
    TrieNode* node = root;
    for (char c : word) {
        int index = c - 'a';
        if (!node->children[index]) {
            return false;
        }
        node = node->children[index];
    }
    return node->isEndOfWord;
}

// 模糊查找（基于Trie树）
bool fuzzySearch(TrieNode* root, const std::string& longString) {
    for (size_t i = 0; i < longString.length(); ++i) {
        for (size_t j = i; j < longString.length(); ++j) {
            std::string subStr = longString.substr(i, j - i + 1);
            if (search(root, subStr)) {
                return true;
            }
        }
    }
    return false;
}

哈希表优化的滑动窗口查找

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

// 计算字符串的哈希值（简单示例，实际可使用更好的哈希函数）
size_t hashFunction(const std::string& str) {
    size_t hash = 0;
    for (char c : str) {
        hash = 31 * hash + c;
    }
    return hash;
}

// 模糊查找（基于哈希表和滑动窗口）
bool fuzzySearchHash(const std::vector<std::string>& subStrings, const std::string& longString) {
    std::unordered_set<size_t> hashSet;
    for (const std::string& subStr : subStrings) {
        hashSet.insert(hashFunction(subStr));
    }

    for (size_t windowSize = 1; windowSize <= longString.length(); ++windowSize) {
        for (size_t i = 0; i <= longString.length() - windowSize; ++i) {
            std::string window = longString.substr(i, windowSize);
            size_t windowHash = hashFunction(window);
            if (hashSet.find(windowHash) != hashSet.end()) {
                return true;
            }
        }
    }
    return false;
}

星途面试题库

面试题：C++ STL find模糊查找的性能优化

知识考点

面试题答案

优化思路

关键代码示例