levenshtein.cpp

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2069085#1
#include "math.h"
#include <algorithm>
#include <complex>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
#define ifor(i, a, b) for (int i = (a); i < (b); i++)
#define rfor(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using namespace std;
typedef long double ld;
typedef long long int lli;
typedef pair<lli, lli> P;
const double eps = 1e-11;
int vex[4] = {1, 0, -1, 0};
int vey[4] = {0, 1, 0, -1};
lli MOD = 1000000007;
int memo[50010];
int n, m;
int c[50040];
int levenshtein(string s1, string s2)
{
    int dp[1010][1010];
    rep(i, 1010) rep(j, 1010) dp[i][j] = MOD;
    dp[0][0] = 0;
    rep(i, s1.size() + 1) rep(j, s2.size() + 1)
    {
        if (i == 0 || j == 0) {
            dp[i][j] = max(i, j);
        } else {
            int p = 0;
            if (s1[i - 1] != s2[j - 1])
                p = 1;
            dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + p);
        }
    }
    return dp[s1.size()][s2.size()];
}
int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    cout << levenshtein(s1, s2) << endl;
}