Почему расстояние Дамерау-Левентшейна показывает разность 2 между словами "привет" и "пливет", если можно заменить букву "л" на "р"?

Проблема в том что символы 'р' и 'л' в кодировке UTF-8 занимают по два байта. Ваш код считает расстояние Левенштейна над байтовыми строками, и чтобы подогнать одну строку под другую нужно поменять два байта, а не один. Для сравнения попробуйте 'privet' и 'plivet'. Всё будет работать как надо.

Замените string на wstring и всё заработает для русского текста:

$ ./a.out
"привет", "пливет": 2
"?@825B", "?;825B": 1
"privet", "plivet": 1
"privet", "plivet": 1

Для этой программы:

// g++ -Wall -Wextra -std=c++11 levenshtein.cpp

#include <iostream>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>

using std::string;
using std::wstring;
using std::min;
using std::vector;

template<typename S>
int Damerau_LevenshteinDistance(S A, S B) {
    size_t n = A.size();
    size_t m = B.size();
    vector<vector<int>> d(n+1, vector<int>(m+1));
    int i;
    int j;
    int l_cost;
    for (i = 0; i <= n; i++) {
        d[i][0] = i;
    }
    for (j = 0; j <= m; j++) {
        d[0][j] = j;
    }
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (A[i-1] == B[j-1] ) {
                l_cost = 0;
            }
            else {
                l_cost = 1;
            }
            d[i][j] = min(
                               d[i-1][j] + 1,         // удаление
                               min(d[i][j-1] + 1,     // вставка
                               d[i-1][j-1] + l_cost)  // замена
                               );
            if ((i > 1) && (j > 1) && (A[i-1] == B[j-2]) && (A[i-2] == B[j-1])) {
                d[i][j] = min(d[i][j], d[i-2][j-2] + l_cost); //транспозиция
            }
        }
    }
    return d[n][m];
}

void test(const string& a, const string& b) {
    std::cout << "\"" << a << "\", \"" << b << "\": " << Damerau_LevenshteinDistance<string>(a, b) << '\n';
}

void wtest(const wstring& a, const wstring& b) {
    std::wcout << L"\"" << a << L"\", \"" << b << L"\": " << Damerau_LevenshteinDistance<wstring>(a, b) << L'\n';
}

int main() {
    test("привет", "пливет");
    wtest(L"привет", L"пливет");
    test("privet", "plivet");
    wtest(L"privet", L"plivet");
}