Levenshtein distance

Levenshtein_distance.cpp

#include <iostream>
#include <string>

#define FOR(i,m,n) for (int i=(m); i<(int)(n) ;i++)

int main() {
  string x = "google";
  string y = "gooogle";

  int size_x = x.length();
  int size_y = y.length();

  int dp[size_x+1][size_y+1];

  FOR(i,0,size_x+1)
    FOR(j,0,size_y+1)
      dp[i][j] = 0;

  FOR(i,0,size_x+1) dp[i][0] = i;
  FOR(i,0,size_y+1) dp[0][i] = i;

  FOR(i,1,size_x+1) {
    FOR(j,1,size_y+1) {
      int cost;
      if (x[i-1] == y[j-1]) cost=0;
      else cost = 1;
      dp[i][j] = dp[i-1][j]+1; // insert
      dp[i][j] = min(dp[i][j], dp[i][j-1]+1); // delete
      dp[i][j] = min(dp[i][j], dp[i-1][j-1]+cost); // swap
    }
  }

  FOR(i,0,size_x+1) {
    FOR(j,0,size_y+1) {
      cout << dp[i][j] << ' ';
    }
    cout << endl;
  }
    
  cout << dp[size_x][size_y] << endl;
}