Pastebin launched a little side project called HostCabi.net, check it out ;-)Don't like ads? PRO users don't see any ads ;-)
Guest

Untitled

By: a guest on Jul 6th, 2012  |  syntax: C++  |  size: 1.62 KB  |  hits: 76  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <map>
  4. #include <string>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. map< vector< string >, int > lev_cache;
  10.  
  11. int levenshtein_distance(string l1, string l2) {
  12.         if (l1 == l2) return 0;
  13.         if (l1 == "" && l2 != "") return l2.length();
  14.         if (l1 != "" && l2 == "") return l1.length();
  15.        
  16.         vector< string > temp; temp.push_back(l1); temp.push_back(l2); //vector< string > temp = {l1, l2};
  17.         if (lev_cache.count(temp) > 0) return lev_cache[temp];
  18.        
  19.         string l1_1, l1_rest, l2_1, l2_rest;
  20.         l1_1 = l1.substr(0,1);
  21.         l1_rest = l1.substr(1);
  22.         l2_1 = l2.substr(0,1);
  23.         l2_rest = l2.substr(1);
  24.         if (l2_1 == l1_1) {
  25.                         int d = levenshtein_distance(l1_rest, l2_rest);
  26.                         temp.clear(); temp.push_back(l1_rest); temp.push_back(l2_rest); //temp = {l1_rest, l2_rest};
  27.                         lev_cache[temp] = d;
  28.                         return d;
  29.         }
  30.         int m1 = levenshtein_distance(l1_rest, l2);
  31.         temp.clear(); temp.push_back(l1_rest); temp.push_back(l2); //temp = {l1_rest, l2};
  32.         lev_cache[temp] = m1;
  33.         int m2 = levenshtein_distance(l1, l2_rest);
  34.         temp.clear(); temp.push_back(l1); temp.push_back(l2_rest); //temp = {l1, l2_rest};
  35.         lev_cache[temp] = m2;
  36.         int m3 = levenshtein_distance(l1_rest, l2_rest);
  37.         temp.clear(); temp.push_back(l1_rest); temp.push_back(l2_rest); //temp = {l1_rest, l2_rest};
  38.         lev_cache[temp] = m3;
  39.         return 1 + min(min(m1, m2), m3);
  40. }
  41.  
  42. int main(int argc, char **argv)
  43. {
  44.         cout << "Distance: " << levenshtein_distance("the quick brown fox jumps over the lazy dog", "pack my box with five dozen liquor jugs") << "\n";
  45.         //cout << "Distance: " << levenshtein_distance("the quick brown fox", "pack my box") << "\n";
  46. }