1 #ifndef ROSE_EditDistance_DamerauLevenshtein_H
2 #define ROSE_EditDistance_DamerauLevenshtein_H
4 #include <EditDistance/Levenshtein.h>
7 namespace EditDistance {
18 if (src.empty() || tgt.empty())
19 return std::max(src.size(), tgt.size());
21 const size_t x = src.size();
22 const size_t y = tgt.size();
23 std::vector<std::vector<size_t> > score(x+2, std::vector<size_t>(y+2, 0));
24 size_t score_ceil = x + y;
25 score[0][0] = score_ceil;
26 for (
size_t i=0; i<=x; ++i) {
28 score[i+1][0] = score_ceil;
30 for (
size_t j=0; j<=y; ++j) {
32 score[0][j+1] = score_ceil;
36 for (
size_t i=0; i<x; ++i)
37 dict.unique_push_zero(src[i]);
38 for (
size_t j=0; j<y; ++j)
39 dict.unique_push_zero(tgt[j]);
41 for (
size_t i=1; i<=x; ++i) {
43 for (
size_t j=1; j<=y; ++j) {
44 size_t i1 = dict[tgt[j-1]];
46 if (src[i-1]==tgt[j-1]) {
47 score[i+1][j+1] = score[i][j];
50 score[i+1][j+1] = std::min(score[i][j], std::min(score[i+1][j], score[i][j+1])) + 1;
53 score[i+1][j+1] = std::min(score[i+1][j+1], score[i1][j1] + (i-i1-1) + 1 + (j-j1-1));
58 return score[x+1][y+1];