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

size_t levenshtein(std::string& a,
                   std::string& b)
{
  using namespace std;
  size_t asize=a.size(), bsize = b.size();

  //Just need two rows at a time
  vector<size_t> prevrow(bsize+1), thisrow(bsize+1);

  for(size_t i = 0; i <= bsize; i++)
    prevrow[i] = i;

  for(size_t i = 1; i <= asize; i ++)
  {
    thisrow[0] = i;
    for(size_t j = 1; j <= bsize; j++)
    {
      thisrow[j] = min(prevrow[j-1] + size_t(a[i-1] != b[j-1]),
                       1 + min(prevrow[j],thisrow[j-1]) );
    }
    swap(thisrow,prevrow);
  }

  return prevrow[bsize];
}