edit-distance.cpp

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

int min3(int a, int b, int c) {
  return min(a, min(b, c));
}

int main() {
  string a, b;
  getline(cin, a);
  getline(cin, b);
  
  int la = a.length();
  int lb = b.length();
  int dp[la+1][lb+1];
  
  for (int i = 0; i <= la; i++) {
    for (int j = 0; j <= lb; j++) {
      if (i == 0) dp[i][j] = j;
      else if (j == 0) dp[i][j] = i;
      else if (a[i-1] == b[j-1]) {
        dp[i][j] = dp[i-1][j-1];
      } else {
        int ins = dp[i][j-1];
        int del = dp[i-1][j];
        int rep = dp[i-1][j-1];
        dp[i][j] = 1 + min3(ins, del, rep);
      }
    }
  }
  
  /* Print out the DP table */
  
  cout << "      ";
  for (char c : b) cout << c << " ";
  cout << endl;
  cout << "  .--";
  for (char c : b) cout << "--";
  cout << endl;
  
  for (int i = 0; i <= la; i++) {
    if (i > 0) cout << a[i-1] << " | ";
    else cout << "  | ";
    for (int j = 0; j <= lb; j++) {
      cout << dp[i][j] << " ";
    }
    cout << endl;
  }
  
  cout << endl << "Edit distance: " << dp[la][lb];
}