Mercurial > hg > toys

comparison levenshtein.c++ @ 2:0748d902784c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 57fc6080db4d
children 56c58a177cde
comparison
equal deleted inserted replaced
1:60954ea75cce 2:0748d902784c
1 #include <string> 1 #include <string>
2 #include <vector> 2 #include <vector>
3 #include <iostream>
3 4
4 using namespace std;
5 5
6 size_t min(size_t x, size_t y) 6 size_t min(size_t x, size_t y)
7 { 7 {
8 return x < y ? x : y; 8 return x < y ? x : y;
9 } 9 }
10 10
11 11
12 size_t levenshtein(const string& a, 12 size_t levenshtein(const std::string& a,
13 const string& b) 13 const std::string& b,
14 size_t m)
14 { 15 {
15 vector<vector<size_t>> matrix(a.size(), vector<size_t>(b.size(), 0)); 16 using namespace std;
17 vector<vector<size_t> > matrix(a.size()+1, vector<size_t>(b.size()+1, 0));
16 18
17 for(size_t i = 0; i < a.size(); i++) 19 for(size_t i = 0; i < a.size()+1; i++)
18 { 20 {
19 matrix[i][0] = i; 21 matrix[i][0] = i;
20 for(size_t j = 0; j < b.size(); j++) 22 for(size_t j = 1; j < b.size()+1; j++)
21 { 23 {
22 if(i == 0) 24 if(i == 0)
23 { 25 {
24 matrix[0][j] = j; 26 matrix[0][j] = j;
25 continue; 27 continue;
26 } 28 }
27 matrix[i][j] = min( matrix[i-1][j-1] + size_t(a[i] != b[j]), 29 matrix[i][j] = min( matrix[i-1][j-1] + size_t(a[i-1] != b[j-1]),
28 1 + min(matrix[i-1][j], 30 1 + min(matrix[i-1][j],
29 matrix[i][j-1])); 31 matrix[i][j-1]));
30 } 32 }
31 } 33 }
32 return matrix[a.size()-1][b.size()-1]; 34 return matrix[a.size()][b.size()];
33 } 35 }