bench.cpp

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
#include <fstream>
#include <chrono>

using namespace std;

struct Node {
    unordered_map<char, int> children;
    int failureLink = 0;
    bool isEnd = false;
    int depth = 0;
};

vector<Node> trie;

void init() {
    trie.clear();
    trie.push_back(Node()); // Root
}

void insert(const string& s) {
    int u = 0;
    for (char c : s) {
        if (trie[u].children.find(c) == trie[u].children.end()) {
            trie.push_back(Node());
            int newNodeIdx = trie.size() - 1;
            trie[newNodeIdx].depth = trie[u].depth + 1;
            trie[u].children[c] = newNodeIdx;
        }
        u = trie[u].children[c];
    }
    trie[u].isEnd = true;
}

int nextState(int u, char c) {
    while (u != 0 && trie[u].children.find(c) == trie[u].children.end()) {
        u = trie[u].failureLink;
    }
    if (trie[u].children.find(c) != trie[u].children.end()) {
        return trie[u].children[c];
    }
    return 0;
}

void buildFailureLinks() {
    queue<int> q;
    for (auto const& [key, v] : trie[0].children) {
        q.push(v);
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (auto const& [charKey, v] : trie[u].children) {
            int f = nextState(trie[u].failureLink, charKey);
            trie[v].failureLink = f;
            q.push(v);
        }
    }
}

long long findPatterns(const string& text) {
    int u = 0;
    long long matches = 0;
    for (char c : text) {
        u = nextState(u, c);
        int temp = u;
        while (temp != 0) {
            if (trie[temp].isEnd) matches++;
            temp = trie[temp].failureLink;
        }
    }
    return matches;
}

int main() {
    ifstream t("war_and_peace.txt");
    string text((istreambuf_iterator<char>(t)), istreambuf_iterator<char>());
    cout << "Text Length: " << text.length() << endl;

    init();

    for(int i=0; i<1000; i++) {
        if (i + 5 < text.length())
             insert(text.substr(i, 4)); 
    }

    auto start = chrono::high_resolution_clock::now();
    
    buildFailureLinks();
    
    long long count = findPatterns(text);
    
    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double> diff = end - start;

    cout << "Matches found: " << count << endl;
    cout << "Time: " << diff.count() << " s" << endl;

    return 0;
}