changeset 2:0748d902784c

Fix off-by-ones, don't use std globally
author Jordi Gutiérrez Hermoso <jordigh@gmail.com>
date Mon, 27 Dec 2010 13:28:19 -0600
parents 60954ea75cce
children 56c58a177cde
files levenshtein.c++ main.c++
diffstat 2 files changed, 11 insertions(+), 10 deletions(-) [+]
line wrap: on
line diff
--- a/levenshtein.c++
+++ b/levenshtein.c++
@@ -1,7 +1,7 @@
 #include <string>
 #include <vector>
+#include <iostream>
 
-using namespace std;
 
 size_t min(size_t x, size_t y)
 {
@@ -9,25 +9,27 @@
 }
 
 
-size_t levenshtein(const string& a,
-                   const string& b)
+size_t levenshtein(const std::string& a,
+                   const std::string& b,
+                   size_t m)
 {
-  vector<vector<size_t>> matrix(a.size(), vector<size_t>(b.size(), 0));
+  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(); i++)
+  for(size_t i = 0; i < a.size()+1; i++)
   {
     matrix[i][0] = i;
-    for(size_t j = 0; j < b.size(); j++)
+    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] != b[j]),
+      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()-1][b.size()-1];
+  return matrix[a.size()][b.size()];
 }
--- a/main.c++
+++ b/main.c++
@@ -4,7 +4,7 @@
 #include <sstream>
 #include <algorithm>
 
-void string_to_upper(std::string& str) 
+void string_to_upper(std::string& str)
 {
   std::transform( str.begin(), str.end(), str.begin(),  &toupper);
 }
@@ -23,7 +23,6 @@
   string phrase = "tihs sententcnes iss nout varrry goud";
   stringstream ss; ss << phrase;
   size_t total_distance = 0;
-
   while( ss >> word)
   {
     string_to_upper(word);