cprover
Loading...
Searching...
No Matches
edit_distance.h
Go to the documentation of this file.
1
11
12#ifndef CPROVER_UTIL_EDIT_DISTANCE_H
13#define CPROVER_UTIL_EDIT_DISTANCE_H
14
15#include "nfa.h"
16
17#include <cstddef>
18#include <string>
19
20#include <util/optional.h>
21
26{
27private:
30 std::vector<state_labelt> final_states;
31
32public:
34 const std::string &string,
35 std::size_t allowed_errors = 2);
36
37 bool matches(const std::string &string) const;
38 optionalt<std::size_t> get_edit_distance(const std::string &string) const;
39
40 void dump_automaton_dot_to(std::ostream &out)
41 {
43 };
44};
45
46#endif // CPROVER_UTIL_EDIT_DISTANCE_H
nonstd::optional< T > optionalt
Definition optional.h:35
Simple automaton that can detect whether a string can be transformed into another with a limited numb...
levenshtein_automatont(const std::string &string, std::size_t allowed_errors=2)
nfat< char >::state_labelt state_labelt
optionalt< std::size_t > get_edit_distance(const std::string &string) const
void dump_automaton_dot_to(std::ostream &out)
bool matches(const std::string &string) const
std::vector< state_labelt > final_states
Very simple NFA implementation Not super performant, but should be good enough for our purposes.
Definition nfa.h:28
std::size_t state_labelt
Definition nfa.h:29
void dump_automaton_dot_to(std::ostream &out) const
Write the automaton structure to out in graphviz dot format.
Definition nfa.h:105