LCS, longest common subsequence

 

static int LCS (String a, String b)
{
    a = "_" + a;
    b = "_" + b;

    int[][] dp = new int[a.length()][b.length()];

    for (int i=1; i<a.length(); i++)
    {
        for (int j=1; j<b.length(); j++)
        {
            if ( a.charAt(i) == b.charAt(j) )
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }

    return dp[a.length()-1][b.length()-1];
}