#include <string>
#include <vector>
#include <iostream>


size_t min(size_t x, size_t y)
{
  return x < y ? x : y;
}


size_t levenshtein(const std::string& a,
                   const std::string& b,
                   size_t m)
{
  using namespace std;
  vector<vector<size_t> > matrix(a.size()+1, vector<size_t>(b.size()+1, 0));

  for(size_t i = 0; i < a.size()+1; i++)
  {
    matrix[i][0] = i;
    for(size_t j = 1; j < b.size()+1; j++)
    {
      if(i == 0)
      {
        matrix[0][j] = j;
        continue;
      }
      matrix[i][j] = min( matrix[i-1][j-1] + size_t(a[i-1] != b[j-1]),
                          1 + min(matrix[i-1][j],
                                  matrix[i][j-1]));
    }
  }
  return matrix[a.size()][b.size()];
}