题解 | #最长公共子串#

class Solution {
public:
string LCS(string str1, string str2) {
int dp[str1.size()]; //以str1[i]、str2[j]结尾的子序列长度，以下简称sub[i][j]
int max = 0, record = -1; //记录最大长度和str1起始位置
for(int i = 0; i < str1.size(); i++) {
dp[i] = str1[i] == str2[0] ? 1 : 0; //初始化sub[i][0]
}
for(int j = 1; j < str2.size(); j++) {
for(int i = str1.size() - 1; i >= 1; i--) { //由于sub[i][j]需要用到sub[i-1][j-1]即dp[i-1]，倒过来循环省去存储dp[i-1]的步骤
if(str1[i] == str2[j]) { //判断末尾字符是否相同
dp[i] = (i == 0 ? 1 : dp[i - 1] + 1);
if(dp[i] > max) { //记录最大长度和开始位置
max = dp[i];
record = i;
}
}
else dp[i] = 0;
}
}
return str1.substr(record - max + 1, max);
}
};