white_box_code.h

Zobrazit dokumentaci tohoto souboru.

//======= Copyright (c) 2026, FIT VUT Brno, All rights reserved. ============//
//
// Purpose:     White Box - suffixový automat
//
// $NoKeywords: $ivs_project_1 $white_box_code.cpp
// $Authors:    Martin Dočekal <idocekal@fit.vutbr.cz>
//              Maksim Aparovich <iaparovich@fit.vut.cz>
// $Date:       $2026-02-09
//============================================================================//
#ifndef SUFFIX_AUTOMATON_HPP
#define SUFFIX_AUTOMATON_HPP
 
#include <string>
#include <unordered_map>
#include <vector>
#include <memory>
#include <cstddef>
#include <optional>
 
struct State {
    size_t len; 
    std::optional<size_t> link; 
    std::unordered_map<char, size_t> next; 
 
    State() : len(0), link(std::nullopt) {}
};
 
 
class SuffixAutomaton {
private:
    std::vector<State> states; 
    size_t last; 
 
public:
 
    SuffixAutomaton();
 
    SuffixAutomaton(const std::string& seq) : SuffixAutomaton() {
        add_sequence(seq);
    }
 
    void add_element(char elem);
 
    void add_sequence(const std::string& seq);
 
    bool step(const size_t state_index, const char& elem, size_t& next_state) const;
 
    const std::unordered_map<char, size_t>& next(const size_t state_index) const;
 
    bool contains(const std::string& seq) const;
 
    std::vector<size_t> topological_sort() const;
 
    std::string longest_direct_continuation(const size_t state_index) const;
 
    size_t size() const;
 
    void clear();
 
    const State& get_state(size_t index) const ;
 
};
 
#endif // SUFFIX_AUTOMATON_HPP
 
/*** Konec souboru white_box_code.h ***/