寻求高性能、可忽略空白符的JavaScript源码C++搜索算法

Given your requirement to ignore whitespace during search (with performance as the top priority), here's a structured solution tailored to C++:

Core Insight #

The problem reduces to checking if the whitespace-stripped version of your pattern is a substring of the whitespace-stripped version of the target JavaScript source. All your example cases align with this: stripping whitespace from both the pattern and the relevant target substring results in identical strings.

Performance-Optimized Options #

1. For Multiple Searches on the Same Target #

If you're searching the same JS source multiple times, preprocess the target once to avoid redundant work:

Step 1: Preprocess the Target

Store a list of indices of non-whitespace characters in the target. This uses less memory than storing the full stripped string while still enabling fast searches.

// Helper to get indices of all non-whitespace characters in the target
std::vector<int> get_non_whitespace_indices(const std::string& target) {
    std::vector<int> indices;
    indices.reserve(target.size()); // Preallocate for efficiency
    for (size_t i = 0; i < target.size(); ++i) {
        if (!std::isspace(static_cast<unsigned char>(target[i]))) {
            indices.push_back(static_cast<int>(i));
        }
    }
    return indices;
}

Step 2: Use Boyer-Moore-Horspool (BMH) Algorithm

BMH is a fast, easy-to-implement substring search algorithm with excellent average-case performance (especially for long patterns). Preprocess your stripped pattern once per search, then run BMH on the non-whitespace indices:

// Build BMH bad character shift table
std::vector<int> build_bmh_shift_table(const std::string& stripped_pattern) {
    const int ALPHABET_SIZE = 256;
    std::vector<int> shift(ALPHABET_SIZE, static_cast<int>(stripped_pattern.size()));
    for (size_t i = 0; i < stripped_pattern.size() - 1; ++i) {
        unsigned char c = static_cast<unsigned char>(stripped_pattern[i]);
        shift[c] = static_cast<int>(stripped_pattern.size() - 1 - i);
    }
    return shift;
}

// Helper to strip whitespace from a string
std::string strip_whitespace(const std::string& s) {
    std::string res;
    res.reserve(s.size()); // Avoid reallocations
    for (char c : s) {
        if (!std::isspace(static_cast<unsigned char>(c))) {
            res += c;
        }
    }
    return res;
}

// Search using precomputed non-whitespace indices
int search_with_preprocessed_target(const std::string& target, const std::string& pattern, const std::vector<int>& non_ws_indices) {
    std::string stripped_pattern = strip_whitespace(pattern);
    const int m = static_cast<int>(stripped_pattern.size());
    const int k = static_cast<int>(non_ws_indices.size());

    if (m == 0) return 0; // Handle empty pattern as needed
    if (m > k) return -1; // Not enough non-whitespace characters to match

    auto shift_table = build_bmh_shift_table(stripped_pattern);

    int i = m - 1;
    while (i < k) {
        int j = m - 1;
        // Compare pattern with non-whitespace characters in target
        while (j >= 0 && target[non_ws_indices[i - (m - 1 - j)]] == stripped_pattern[j]) {
            --j;
        }
        if (j == -1) {
            // Return the start position in the original target
            return non_ws_indices[i - m + 1];
        }
        // Calculate shift using bad character rule
        unsigned char bad_char = static_cast<unsigned char>(target[non_ws_indices[i]]);
        i += shift_table[bad_char];
    }
    return -1; // No match found
}

2. For Single Searches on a Target #

If you only need to search once, avoid preprocessing the entire target. Instead:

• Strip whitespace from the pattern first.
• Use a modified BMH algorithm that skips whitespace in the target on the fly (saves memory for large targets).

// Modified BMH to skip whitespace in target
int search_single_pass(const std::string& target, const std::string& pattern) {
    std::string stripped_pattern = strip_whitespace(pattern);
    const int m = static_cast<int>(stripped_pattern.size());
    const int n = static_cast<int>(target.size());

    if (m == 0) return 0;
    if (m > n) return -1;

    auto shift_table = build_bmh_shift_table(stripped_pattern);

    // Helper to find the next non-whitespace character going backward
    auto find_prev_non_ws = [&](int pos) -> int {
        while (pos >= 0 && std::isspace(static_cast<unsigned char>(target[pos]))) {
            --pos;
        }
        return pos;
    };

    // Start at the m-th non-whitespace character from the end
    int current_pos = find_prev_non_ws(n - 1);
    int count = 1;
    while (current_pos != -1 && count < m) {
        current_pos = find_prev_non_ws(current_pos - 1);
        ++count;
    }
    if (current_pos == -1) return -1;

    while (true) {
        int p_idx = m - 1;
        int t_idx = current_pos;
        bool match = true;

        while (p_idx >= 0 && t_idx >= 0) {
            t_idx = find_prev_non_ws(t_idx);
            if (t_idx == -1 || target[t_idx] != stripped_pattern[p_idx]) {
                match = false;
                break;
            }
            --p_idx;
            --t_idx;
        }

        if (match && p_idx == -1) {
            // Find the start of the match in original target
            int start = t_idx + 1;
            while (start < n && std::isspace(static_cast<unsigned char>(target[start]))) {
                ++start;
            }
            return start;
        }

        // Calculate shift using bad character
        int bad_char_pos = find_prev_non_ws(current_pos);
        if (bad_char_pos == -1) break;
        unsigned char bad_char = static_cast<unsigned char>(target[bad_char_pos]);
        int shift = shift_table[bad_char];

        // Move current_pos forward by shift
        current_pos = bad_char_pos + shift;
        // Find the m-th non-whitespace character from new position
        current_pos = find_prev_non_ws(current_pos + m - 1);
        count = 1;
        while (current_pos != -1 && count < m) {
            current_pos = find_prev_non_ws(current_pos - 1);
            ++count;
        }
        if (current_pos == -1) break;
    }

    return -1;
}

Key Performance Notes #

• BMH vs. Other Algorithms: BMH outperforms KMP in most real-world scenarios due to its simpler shift rules and better cache behavior. For very short patterns, std::string::find (which may use an optimized internal algorithm) could be comparable, but BMH is more consistent for longer patterns.
• Unicode Considerations: If your JS source contains Unicode whitespace (e.g., non-breaking spaces), replace std::isspace with a Unicode-aware whitespace check (e.g., using a custom function that handles Unicode code points).
• Memory Efficiency: Preprocessing non-whitespace indices uses O(k) memory where k is the number of non-whitespace characters in the target—this is more efficient than storing the full stripped string if you only need match positions.

内容的提问来源于stack exchange，提问作者Oleg