Method levenshteinDistance

context/ChangesManager.cpp:454–485

}

int ChangesManager::levenshteinDistance(const QString &s1, const QString &s2) const
{
    const int len1 = s1.length();
    const int len2 = s2.length();
    
    const int MAX_LENGTH = 10000;
    if (len1 > MAX_LENGTH || len2 > MAX_LENGTH) {
        return qAbs(len1 - len2) + qMin(len1, len2) / 2;
    }
    
    QVector<QVector<int>> d(len1 + 1, QVector<int>(len2 + 1));
    
    for (int i = 0; i <= len1; ++i) {
        d[i][0] = i;
    }
    for (int j = 0; j <= len2; ++j) {
        d[0][j] = j;
    }
    
    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
            d[i][j] = std::min({
                d[i - 1][j] + 1,
                d[i][j - 1] + 1,
                d[i - 1][j - 1] + cost
            });
        }
    }
    
    return d[len1][len2];
}

QString ChangesManager::findBestMatchLineBased(
    const QString &fileContent,