String Matching

main.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cassert>
#include <random>
#include <chrono>

auto NaiveMatch(const std::string &pattern, const std::string &text) -> int {
    auto pattern_length = pattern.size();
    auto text_length = text.size();

    for (int i = 0; i <= text_length - pattern_length; ++i) {
        int j = 0;
        for (; j < pattern_length; ++j) {
            if (text[i + j] != pattern[j]) {
                break;
            }
        }
        if (j == pattern_length) {
            return i;
        }
    }
    return -1;
}

auto RKMatch(const std::string &pattern, const std::string &text) -> int {
    auto q = 13; // A prime number for modulus
    auto pattern_length = pattern.size();
    auto text_length = text.size();
    auto alphabet_size = 26; // Assuming ASCII character set

    long long pattern_fingerprint = 0;
    std::vector<long long> text_fingerprints;
    text_fingerprints.assign(text_length - pattern_length + 1, 0);

    // prepare the fingerprints for the first window
    for (int i = 0; i < pattern_length; ++i) {
        // 同时也计算模式串的指纹值
        pattern_fingerprint = (alphabet_size * pattern_fingerprint + pattern[i]) % q;
        text_fingerprints[0] = (alphabet_size * text_fingerprints[0] + text[i]) % q;
    }

    if (pattern_fingerprint == text_fingerprints[0]) {
        if (text.substr(0, pattern_length) == pattern) {
            return 0;
        }
    }

    // h = d^(m-1) % q
    auto h = static_cast<long long>(std::pow(alphabet_size, pattern_length - 1)) % q;

    for (int i = 1; i < text_fingerprints.size(); ++i) {
        auto old_char = text[i - 1];
        auto new_char = text[i + pattern_length - 1];
        text_fingerprints[i] = (alphabet_size * (text_fingerprints[i - 1] - old_char * h) + new_char) % q;

        if (text_fingerprints[i] < 0) {
            text_fingerprints[i] += q;
        }

        if (pattern_fingerprint == text_fingerprints[i]) {
            if (text.substr(i, pattern_length) == pattern) {
                return i;
            }
        }
    }

    return -1; // Pattern not found
}

auto ComputeTransitionTable(const std::string &pattern) -> std::vector<std::vector<int> > {
    int pattern_length = pattern.size();
    int alphabet_size = 26; // Assuming ASCII character set

    std::vector<std::vector<int> > transition_table(pattern_length + 1, std::vector<int>(alphabet_size, 0));

    for (int q = 0; q <= pattern_length; ++q) {
        for (int a = 0; a < alphabet_size; ++a) {
            int k = std::min(pattern_length, q + 1);
            std::string current_str = pattern.substr(0, q) + static_cast<char>(a + 'a');
            while (k > 0) {
                auto prefix = pattern.substr(0, k);
                auto suffix = current_str.substr(current_str.length() - k, k);
                if (prefix == suffix) {
                    break;
                }
                --k;
            }
            transition_table[q][a] = k;
        }
    }

    return transition_table;
}

auto GenerateNextVector(const std::string &pattern) -> std::vector<int>;

auto FiniteAutomatonMatch(const std::string &pattern, const std::string &text) -> int {
    // Precompute the transition table for the pattern
    // auto ComputeTransitionTable = [&]() {
    //     int pattern_length = pattern.size();
    //     int alphabet_size = 26; // Assuming ASCII character set
    //
    //     std::vector<std::vector<int> > transition_table(pattern_length + 1, std::vector<int>(alphabet_size, 0));
    //
    //     for (int q = 0; q <= pattern_length; ++q) {
    //         for (int a = 0; a < alphabet_size; ++a) {
    //             int k = std::min(pattern_length, q + 1);
    //             std::string current_str = pattern.substr(0, q) + static_cast<char>(a + 'a');
    //             while (k > 0) {
    //                 auto prefix = pattern.substr(0, k);
    //                 auto suffix = current_str.substr(current_str.length() - k, k);
    //                 if (prefix == suffix) {
    //                     break;
    //                 }
    //                 --k;
    //             }
    //             transition_table[q][a] = k;
    //         }
    //     }
    //
    //     return transition_table;
    // };

    auto ONComputeTransitionTable = [&]() {
        int pattern_length = pattern.size();
        int alphabet_size = 26; // Assuming ASCII character set

        std::vector<std::vector<int>> transition_table(pattern_length + 1, std::vector<int>(alphabet_size, 0));

        auto next = GenerateNextVector(pattern);

        for (int q = 0; q <= pattern_length; ++q) {
            for (int a = 0; a < alphabet_size; ++a) {
                auto current_char = static_cast<char>(a + 'a');

                // 如果正好匹配则状态转移到 q + 1，否则根据 next 数组回退到合适的位置
                if (q < pattern_length && current_char == pattern[q]) {
                    transition_table[q][a] = q + 1;
                } else {
                    auto k = q;

                    // 寻找符合 current_char 的最长后缀长度
                    while (k > 0 && current_char != pattern[k]) {
                        k = next[k - 1];
                    }

                    // 有匹配则设置为后缀长度（后缀索引 + 1），否则设置为 0
                    if (current_char == pattern[k]) {
                        transition_table[q][a] = k + 1;
                    } else {
                        transition_table[q][a] = 0;
                    }
                }
            }
        }

        return transition_table;
    };

    // auto transition_table = ComputeTransitionTable(pattern);
    auto transition_table = ONComputeTransitionTable();
    int state = 0;
    for (auto i = 0; i < text.size(); ++i) {
        char current_char = text[i];
        if (current_char < 'a' || current_char > 'z') {
            continue; // Skip characters outside the assumed alphabet
        }
        state = transition_table[state][current_char - 'a'];
        if (state == pattern.size()) {
            return i - pattern.size() + 1; // Pattern found at this index
        }
    }
    return -1; // Pattern not found
}

auto GenerateNextVector(const std::string &pattern) -> std::vector<int> {
    int pattern_length = pattern.size();
    std::vector<int> next(pattern_length, 0);
    int suffix_length = 0;

    for (int i = 1; i < pattern_length; ++i) {
        while (suffix_length > 0 && pattern[i] != pattern[suffix_length]) {
            suffix_length = next[suffix_length - 1];
        }
        if (pattern[i] == pattern[suffix_length]) {
            ++suffix_length;
        }
        next[i] = suffix_length;
    }

    return next;
}

auto KMPMatch(const std::string &pattern, const std::string &text) -> int {
    auto next = GenerateNextVector(pattern);
    int suffix_length = 0; // Index for pattern

    for (int i = 0; i < text.size(); ++i) {
        while (suffix_length > 0 && text[i] != pattern[suffix_length]) {
            suffix_length = next[suffix_length - 1];
        }
        if (text[i] == pattern[suffix_length]) {
            ++suffix_length;
        }
        if (suffix_length == pattern.size()) {
            return i - pattern.size() + 1; // Pattern found at this index
        }
    }

    return -1; // Pattern not found
}

auto GenerateRandomString(int length) -> std::string {
    const std::string characters = "abcdefghijklmnopqrstuvwxyz";
    std::random_device rd;
    std::mt19937 generator(rd());
    std::uniform_int_distribution<> distribution(0, characters.size() - 1);

    std::string random_string;
    for (int i = 0; i < length; ++i) {
        random_string += characters[distribution(generator)];
    }
    return random_string;
}

auto GetPatterFromRandomString(const std::string &random_string, int pattern_length) -> std::string {
    if (pattern_length > random_string.size()) {
        throw std::invalid_argument("Pattern length cannot be greater than the random string length.");
    }
    std::random_device rd;
    std::mt19937 generator(rd());
    std::uniform_int_distribution<> distribution(0, random_string.size() - pattern_length);
    auto random_pos = distribution(generator);
    return random_string.substr(random_pos, pattern_length);
}

int main() {
    auto n = 10;
    auto text_length = 10000;
    auto pattern_length = 50;

    long long total_naive_time = 0;
    long long total_rk_time = 0;
    long long total_fa_time = 0;
    long long total_kmp_time = 0;

    std::cout << "Running Benchmark (" << n << " rounds)..." << std::endl;

    for (int round = 0; round < n; ++round) {
        // std::string text = GenerateRandomString(text_length);
        // std::string pattern = GetPatterFromRandomString(text, pattern_length);

        std::string text(text_length, 'a');
        std::string pattern(pattern_length - 1, 'a');
        pattern += 'b';

        auto start = std::chrono::high_resolution_clock::now();
        int ans_naive = NaiveMatch(pattern, text);
        auto end = std::chrono::high_resolution_clock::now();
        total_naive_time += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

        start = std::chrono::high_resolution_clock::now();
        int ans_rk = RKMatch(pattern, text);
        end = std::chrono::high_resolution_clock::now();
        total_rk_time += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

        start = std::chrono::high_resolution_clock::now();
        int ans_fa = FiniteAutomatonMatch(pattern, text);
        end = std::chrono::high_resolution_clock::now();
        total_fa_time += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

        start = std::chrono::high_resolution_clock::now();
        int ans_kmp = KMPMatch(pattern, text);
        end = std::chrono::high_resolution_clock::now();
        total_kmp_time += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

        assert(ans_rk == ans_naive);
        assert(ans_fa == ans_naive);
        assert(ans_kmp == ans_naive);
    }

    std::cout << "\n================= BENCHMARK RESULTS =================" << std::endl;
    std::cout << "Text Length: " << text_length << " | Pattern Length: " << pattern_length << " | Total Rounds: " << n
            << "\n" << std::endl;
    std::cout << "1. Naive Approach     : " << total_naive_time / 1000.0 << " ms" << std::endl;
    std::cout << "2. Rabin-Karp (RK)    : " << total_rk_time / 1000.0 << " ms" << std::endl;
    std::cout << "3. Finite Automaton   : " << total_fa_time / 1000.0 << " ms" << std::endl;
    std::cout << "4. KMP Algorithm      : " << total_kmp_time / 1000.0 << " ms" << std::endl;
    std::cout << "=====================================================" << std::endl;

    return 0;
}