https://en.wikipedia.org/wiki/Edit_distance https://en.wikipedia.org/wiki/Levenshtein_distance
| 217 | // https://en.wikipedia.org/wiki/Edit_distance |
| 218 | // https://en.wikipedia.org/wiki/Levenshtein_distance |
| 219 | int EditDistance(const std::string& a, const std::string& b) { |
| 220 | int n = a.size(); |
| 221 | int m = b.size(); |
| 222 | if ((n == 0) || (m == 0)) { |
| 223 | return (n == 0) ? m : n; |
| 224 | } |
| 225 | EditDistanceMatrix matrix(m, n); |
| 226 | matrix.At(0, 0) = (a[0] == b[0]) ? 0 : 1; |
| 227 | for (size_t i = 1; i < a.size(); i++) { |
| 228 | matrix.At(0, i) = matrix.At(0, i - 1) + 1; |
| 229 | } |
| 230 | for (size_t j = 1; j < b.size(); j++) { |
| 231 | matrix.At(j, 0) = matrix.At(j - 1, 0) + 1; |
| 232 | } |
| 233 | for (size_t j = 1; j < b.size(); j++) { |
| 234 | for (size_t i = 1; i < a.size(); i++) { |
| 235 | int min = MinOfThreeNum(matrix.At(j - 1, i - 1), matrix.At(j, i - 1), matrix.At(j - 1, i)); |
| 236 | if (a[i] == b[j]) { |
| 237 | matrix.At(j, i) = min; |
| 238 | } else { |
| 239 | matrix.At(j, i) = min + 1; |
| 240 | } |
| 241 | } |
| 242 | } |
| 243 | return matrix.At(m - 1, n - 1); |
| 244 | } |
| 245 | |
| 246 | } // namespace tera |