Edit Distance (Levenshtein Distance)

Edit distance is the minimum number of unit-cost insertions, deletions and replacements transforming one string into another. Prefix states capture which characters have been consumed. The program also prints an alignment-style edit script, so every operation has an unambiguous meaning without mutable string-index confusion. KEEP consumes a matching source character at zero cost.

Prerequisites: LCS prefix states; reconstruction.

Build the idea

1. Recognize the repeated subproblems

   An unrestricted operation search revisits the same alignment of source and target prefixes through many histories. The remaining transformation depends on both prefix lengths, not on the sequence of edits already used. For strings up to 1000 characters, a million prefix states are feasible. Arbitrary costs or transpositions change the recurrence and must be modeled separately.

2. Define the state

   dp[i][j] is minimum edit cost from source prefix a[0…i) to target prefix b[0…j). A deletion consumes only a, an insertion produces only b, and a keep/replacement consumes both. This alignment interpretation is also how the printed script is replayed: accumulate the produced target while advancing the source pointer when consumed.

3. Derive the transition

   The final alignment action is delete a[i−1], insert b[j−1], or pair them at cost zero if equal and one otherwise. Take the minimum of the corresponding predecessor plus action cost. These cases account for every final alignment column; concatenating a predecessor script with its action realizes each candidate. KEEP rows are printed but do not contribute to edit count.

   $$\mathrm{dp}\left[i\right]\left[j\right]=\min \left(\mathrm{dp}\right[i-1\left]\right[j]+1,\mathrm{dp}[i\left]\right[j-1]+1,\mathrm{dp}[i-1\left]\right[j-1]+[a[i-1]\ne b[j-1]\left]\right)$$

4. Base cases and computation order

   dp[i][0]=i because every source character must be deleted; dp[0][j]=j because every target character must be inserted. Fill increasing prefixes. Backtrack matching characters first, then an attaining replacement, deletion or insertion, collect rows backward and reverse. The operation order consumes the original source left-to-right rather than referring to indices that shift after edits.

5. Correctness and invariant

   Induct on i+j using the exhaustive final-action partition. Each candidate transforms the required prefixes and no optimal script can avoid ending in one of those actions. Backtracking uses an attaining predecessor, so the number of non-KEEP rows equals the computed distance. The elementary operations have nonnegative unit costs; a different operation system needs a new completeness argument.

6. Work the example

   Source cat and target cut differ only in their middle letter. The script KEEP c, REPLACE a u, KEEP t has cost 1. The prefix table below shows that the empty row/column are not zero except at the origin. Replacing those boundaries by zeros would permit characters to appear or disappear for free.

   source / target	empty	c	cu	cut
   empty	0	1	2	3
   c	1	0	1	2
   ca	2	1	1	2
   cat	3	2	2	1

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
int main(){
    std::string a,b;
    std::getline(std::cin,a);
    std::getline(std::cin,b);
    int n=a.size(),m=b.size();
    std::vector<std::vector<int>>dp(n+1,std::vector<int>(m+1));
    for(int i=0;i<=n;++i){
        dp[i][0]=i;
    }
    for(int j=0;j<=m;++j){
        dp[0][j]=j;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            dp[i][j]=
                std::min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+(a[i-1]!=b[j-1])});
        }
    }
    std::vector<std::string>operations;
    int i=n,j=m;
    while(i||j){
        if(i&&j&&a[i-1]==b[j-1]){
            operations.push_back("KEEP "+a.substr(i-1,1));
            --i;
            --j;
        }
        else if(i&&j&&dp[i][j]==dp[i-1][j-1]+1){
            operations.push_back("REPLACE "+a.substr(i-1,1)+" "+b.substr(j-1,1));
            --i;
            --j;
        }
        else if(i&&dp[i][j]==dp[i-1][j]+1){
            operations.push_back("DELETE "+a.substr(i-1,1));
            --i;
        }
        else{
            operations.push_back("INSERT "+b.substr(j-1,1));
            --j;
        }
    }
    std::reverse(operations.begin(),operations.end());
    std::cout<<dp[n][m]<<'\n';
    for(auto op:operations){
        std::cout<<op<<'\n'; // Read left-to-right, consuming source on KEEP/DELETE/REPLACE.
    }
}

Complexity analysis

O(nm) states/time and O(nm) table space; three constant transitions per state. Reconstruction/output takes O(n+m). A distance-only rolling-row version uses O(min(n, m)) memory but does not retain this direct alignment backtrack.

Example input and output

Read source and target as two lowercase-letter lines, length 0..1000. Print unit edit distance, then alignment operations KEEP c, DELETE c, INSERT c or REPLACE old new. KEEP/DELETE/REPLACE consume one source character; KEEP/INSERT/REPLACE append a target character.

Input

cat
cut

Output

1
KEEP c
REPLACE a u
KEEP t

Source cat and target cut differ only in their middle letter. The script KEEP c, REPLACE a u, KEEP t has cost 1. The prefix table below shows that the empty row/column are not zero except at the origin. Replacing those boundaries by zeros would permit characters to appear or disappear for free.

Practical applications

Use for approximate sequence comparison and minimal edit scripts under the specified costs. Weighted edits and transpositions require modified transitions. Very long strings with small distance may permit banded or specialized algorithms instead of the full table.

Check your understanding

Why is dp[i][0]=i rather than zero?

Put it into practice

Replay the output operations and verify both the produced target and edit count.