C++ Program: Levenshtein Distance (Edit Distance) Algorithm

Levenshtein Distance (Edit Distance) คือจำนวน Operation น้อยที่สุดเพื่อแปลง String หนึ่งเป็นอีก String หนึ่ง โดย Operation มี 3 แบบ: Insert, Delete, Substitute (แทนที่)

ตัวอย่าง

"cat" → "mat": 1 (Substitute 'c'→'m')
"kitten" → "sitting": 3 (k→s, e→i, +g)
"sunday" → "saturday": 3 (un→atur, +r)

Dynamic Programming Approach

DP Table dp[i][j] = Edit Distance ของ s1[0..i-1] และ s2[0..j-1]

Recurrence

if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]           // Match, no cost
else: dp[i][j] = 1 + min(
    dp[i-1][j],   // Delete from s1
    dp[i][j-1],   // Insert to s1
    dp[i-1][j-1]  // Substitute
)

Base Cases

• dp[0][j] = j (Insert j chars)
• dp[i][0] = i (Delete i chars)

โค้ด C++ (Basic + Optimized)

Version 1: Full DP Table (O(MN) Space)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int levenshtein(const string& s1, const string& s2) {
    int m = s1.length(), n = s2.length();
    vector> dp(m + 1, vector(n + 1));
    
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
            }
        }
    }
    return dp[m][n];
}

Version 2: Space Optimized (O(min(M,N)) Space)

int levenshteinOptimized(const string& s1, const string& s2) {
    // Ensure s1 is shorter for less space
    if (s1.length() > s2.length()) return levenshteinOptimized(s2, s1);
    
    int m = s1.length(), n = s2.length();
    vector prev(m + 1), curr(m + 1);
    
    for (int i = 0; i <= m; i++) prev[i] = i;
    
    for (int j = 1; j <= n; j++) {
        curr[0] = j;
        for (int i = 1; i <= m; i++) {
            if (s1[i-1] == s2[j-1]) {
                curr[i] = prev[i-1];
            } else {
                curr[i] = 1 + min({prev[i], curr[i-1], prev[i-1]});
            }
        }
        swap(prev, curr);
    }
    return prev[m];
}

Version 3: Reconstruct Operations (Backtrace)

vector getOperations(const string& s1, const string& s2) {
    int m = s1.length(), n = s2.length();
    vector> dp(m + 1, vector(n + 1));
    vector> op(m + 1, vector(n + 1)); // 'M','I','D','S'
    
    for (int i = 0; i <= m; i++) { dp[i][0] = i; op[i][0] = 'D'; }
    for (int j = 0; j <= n; j++) { dp[0][j] = j; op[0][j] = 'I'; }
    op[0][0] = ' ';
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
                op[i][j] = 'M'; // Match
            } else {
                int del = dp[i-1][j];
                int ins = dp[i][j-1];
                int sub = dp[i-1][j-1];
                int best = min({del, ins, sub});
                dp[i][j] = 1 + best;
                if (best == del) op[i][j] = 'D';
                else if (best == ins) op[i][j] = 'I';
                else op[i][j] = 'S';
            }
        }
    }
    
    // Backtrace
    vector ops;
    int i = m, j = n;
    while (i > 0 || j > 0) {
        if (op[i][j] == 'M') { i--; j--; ops.push_back("Match " + string(1, s1[i])); }
        else if (op[i][j] == 'S') { i--; j--; ops.push_back("Substitute " + string(1, s1[i]) + "→" + string(1, s2[j])); }
        else if (op[i][j] == 'D') { i--; ops.push_back("Delete " + string(1, s1[i])); }
        else if (op[i][j] == 'I') { j--; ops.push_back("Insert " + string(1, s2[j])); }
        else if (i > 0) { i--; ops.push_back("Delete " + string(1, s1[i])); }
        else { j--; ops.push_back("Insert " + string(1, s2[j])); }
    }
    reverse(ops.begin(), ops.end());
    return ops;
}

ตัวอย่างการรัน

int main() {
    string s1 = "tutorials";
    string s2 = "point";
    
    cout << "Levenshtein Distance: " << levenshtein(s1, s2) << "\n";
    cout << "Optimized: " << levenshteinOptimized(s1, s2) << "\n";
    
    auto ops = getOperations(s1, s2);
    cout << "Operations:\n";
    for (auto& o : ops) cout << "  " << o << "\n";
    
    return 0;
}

ผลลัพธ์

Levenshtein Distance: 8
Optimized: 8
Operations:
  Delete t
  Delete u
  Delete t
  Delete o
  Delete r
  Delete i
  Delete a
  Substitute l→p
  Substitute s→o
  Match i
  Match n
  Match t

Variants & Related Algorithms

Applications

• Spell Checkers, Autocorrect
• DNA Sequence Alignment (Bioinformatics)
• Plagiarism Detection
• Fuzzy String Matching / Search
• OCR Post-correction
• Version Control Diff

C++ Program: Implement Caesar Cipher (Shift Cipher)

C++ Program: Finite State Automaton (FSA) Based String Search