Mercurial > hg > toys
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);