edit_distance.h

Go to the documentation of this file.

 
#ifndef CPROVER_UTIL_EDIT_DISTANCE_H
#define CPROVER_UTIL_EDIT_DISTANCE_H
 
#include "nfa.h"
 
#include <cstddef>
#include <optional>
#include <string>

struct levenshtein_automatont
{
private:
  nfat<char> nfa;
  using state_labelt = nfat<char>::state_labelt;
  std::vector<state_labelt> final_states;
 
public:
  levenshtein_automatont(
    const std::string &string,
    std::size_t allowed_errors = 2);
 
  bool matches(const std::string &string) const;
  std::optional<std::size_t> get_edit_distance(const std::string &string) const;
 
  void dump_automaton_dot_to(std::ostream &out)
  {
    nfa.dump_automaton_dot_to(out);
  };
};
 
#endif // CPROVER_UTIL_EDIT_DISTANCE_H