Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Jul 7th, 2012  |  syntax: C++  |  size: 1.29 KB  |  views: 41  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. int levenshtein_distance(const string& s1, const string& s2) {
  8.   int len1 = s1.size();
  9.   int len2 = s2.size();
  10.   // Put the shorter string first to save memory.
  11.   if(len2 < len1)
  12.     return levenshtein_distance(s2, s1);
  13.   int row, col;
  14.   // costs[i] will be the cost of editing s1.substr(0, i) to s2.substr(0, row)
  15.   vector<int> costs(len1 + 1);
  16.   for(col = 0; col <= len1; ++col)
  17.     // Cost of editing s1.substr(0, col) to "" is col * deletions.
  18.     costs[col] = col;
  19.   // previous_costs[i] will be the cost of
  20.   // editing s1.substr(0, i) to s2.substr(0, row-1)
  21.   vector<int> previous_costs(len1 + 1);
  22.   for(row = 1; row <= len2; ++row) {
  23.     previous_costs.swap(costs);  // fast alternative to previous_costs = costs
  24.     // Cost of editing "" to s2.subst(0, row) is row * insertions.
  25.     costs[0] = row;
  26.     for(col = 1; col <= len1; ++col)
  27.       costs[col] = min(min(
  28.           costs[col-1] + 1,  // Cost of removing the letter s1[col-1].
  29.           previous_costs[col] + 1),  // Cost of adding the letter s2[row-1].
  30.           previous_costs[col-1] + (   // Cost of replacing
  31.             (s1[col-1] == s2[row-1]) ? 0 : 1));  // s1[col-1] with s2[row-1].
  32.   }
  33.   return costs[len1];
  34. }