fork(8) download
copy 
  1. #include <string>
  2. #include <vector>
  3. #include <numeric>
  4. #include <algorithm>
  5. #include <iostream>
  6.  
  7. std::size_t levenshtein_distance( std::string first, std::string second )
  8. {
  9.     if( second.size() < first.size() ) std::swap(first,second) ;
  10.     std::vector<std::size_t> current( second.size()+1 ), previous(current) ;
  11.     std::iota( previous.begin(), previous.end(), 0 ) ;
  12.  
  13.     for( std::size_t i = 0 ; i < first.size() ; ++i )
  14.     {
  15.         current[0] = i+1 ;
  16.         for( std::size_t j = 0 ; j < second.size() ; ++j )
  17.         {
  18.             current[j+1] = std::min( std::min( current[j], previous[j+1]) + 1,
  19.                                      previous[j] + ( first[i] != second[j] ) ) ;
  20.         }
  21.         current.swap(previous);
  22.     }
  23.     return previous.back() ;
  24. }
  25.  
  26. std::vector<std::string> nearest_words( const std::string& word, const std::vector<std::string>& dict )
  27. {
  28.     constexpr std::size_t MAX_DISTANCE = 5 ;
  29.     std::vector<std::string> nearest[MAX_DISTANCE+1] ;
  30.     for( const std::string match : dict )
  31.     {
  32.         std::size_t dist = levenshtein_distance( word, match ) ;
  33.         if( dist <= MAX_DISTANCE ) nearest[dist].push_back(match) ;
  34.     }
  35.  
  36.     for( const auto& seq : nearest ) if( !seq.empty() ) return std::move(seq) ;
  37.     return {} ;
  38. }
  39.  
  40. int main()
  41. {
  42.     const std::vector<std::string>& dict { "mess", "less", "plus", "pious", "messes", "misses", "lessen", "listen" } ;
  43.     const std::string test[] = { "mises", "missse", "mesten", "pius" } ;
  44.     for( const std::string& word : test )
  45.     {
  46.         std::cout << word << " => " ;
  47.         for( const auto& nearest : nearest_words( word, dict ) ) std::cout << nearest << ' ' ;
  48.         std::cout << '\n' ;
  49.     }
  50. }
  51.  
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
mises => misses 
missse => misses 
mesten => messes lessen listen 
pius => plus pious
https://ideone.com/tGHyow
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!