buildtrie.cpp

void FSM::buildTrie()
{
    int newState = 1;

    for (size_t i = 0; i < this->strings.size(); ++i) {
        std::string s = this->strings[i];
        extend(s, &newState);
    }

    for (size_t i = 0; i < MAX_CHAR; ++i) {
        if (go(0, static_cast<char>(i)) == -1) {
            this->trie[0][i] = 0;
        }
    }
}

/**
 * @brief Adds a string to the trie.
 * @param s The string to be added.
 * @param newState The state of the trie prior to the addition.
 */
void FSM::extend(const std::string& s, int* newState)
{
    int state = 0;
    size_t j = 0;

    while (go(state, s[j]) != -1) {
        state = go(state, s[j]);
        j++;
    }
    for (size_t i = j; i < s.size(); ++i) {
        *newState = *newState + 1;
        this->trie[static_cast<size_t>(state)][static_cast<size_t>(s[i])] = *newState;
        state = *newState;
    }
    this->outputs.emplace(state, vs { s });
}