NC127 #最长公共子串#
最长公共子串
http://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac
经典的动态规划题目。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); } };