#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>

std::size_t levenshtein_distance( std::string first, std::string second )
{
    if( second.size() < first.size() ) std::swap(first,second) ;
    std::vector<std::size_t> current( second.size()+1 ), previous(current) ;
    std::iota( previous.begin(), previous.end(), 0 ) ;

    for( std::size_t i = 0 ; i < first.size() ; ++i )
    {
        current[0] = i+1 ;
        for( std::size_t j = 0 ; j < second.size() ; ++j )
        {
            current[j+1] = std::min( std::min( current[j], previous[j+1]) + 1,
                                     previous[j] + ( first[i] != second[j] ) ) ;
        }
        current.swap(previous);
    }
    return previous.back() ;
}

std::vector<std::string> nearest_words( const std::string& word, const std::vector<std::string>& dict )
{
    constexpr std::size_t MAX_DISTANCE = 5 ;
    std::vector<std::string> nearest[MAX_DISTANCE+1] ;
    for( const std::string match : dict )
    {
        std::size_t dist = levenshtein_distance( word, match ) ;
        if( dist <= MAX_DISTANCE ) nearest[dist].push_back(match) ;
    }

    for( const auto& seq : nearest ) if( !seq.empty() ) return std::move(seq) ;
    return {} ;
}

int main()
{
    const std::vector<std::string>& dict { "mess", "less", "plus", "pious", "messes", "misses", "lessen", "listen" } ;
    const std::string test[] = { "mises", "missse", "mesten", "pius" } ;
    for( const std::string& word : test )
    {
        std::cout << word << " => " ;
        for( const auto& nearest : nearest_words( word, dict ) ) std::cout << nearest << ' ' ;
        std::cout << '\n' ;
    }
}