NC127 #最长公共子串#

经典的动态规划题目。
dp[i][j]表示以字符串str1 i位置结尾，以字符串str2 j位置结尾的公共字串的长度。
状态转移方程：
dp[i][j] = dp[i -1][j - 1] + 1, str1[i] == str2[j]
dp[i][j] = 0, str1[i] != str2[j]

class Solution {
public:
    string LCS(string str1, string str2) {
        int len1 = str1.size(), len2 = str2.size(), max = 0, endpos = 0;
        int dp[len1][len2];
        memset(dp, 0, sizeof(int));
        for(int i = 0; i < len1; i++)
        {
            dp[i][0] = str1[i] == str2[0];
            if(dp[i][0] > max)
            {
                max = dp[i][0];
                endpos = i;
            }
        }
        for(int i = 0; i < len2; i++)
        {
            dp[0][i] = str1[0] == str2[i];
            if(dp[0][i] > max)
            {
                max = dp[0][i];
                endpos = 0;
            }
        }
        for(int i = 1; i < len1; i++)
        {
            for(int j = 0; j < len2; j++)
            {
                if(str1[i] == str2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = 0;
                if(dp[i][j] > max)
                {
                    max = dp[i][j];
                    endpos = i;
                }
            }
        }
        if(max == 0) return "";
        return str1.substr(endpos - max + 1, max);
    }
};