题解 | #最长公共子串#
最长公共子串
https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac
动规：只要将当前的子序列最大长度记录在dp数组中即可，若是两者不相等，那么此时dp数组对应的值为零
class Solution {
public:
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
// write code here
//最长的公共子序列，初始化序列
vector<vector<int> > dp(s1.size() + 1, vector<int>(s2.size() + 1,0));
int res = 0;
int pos = 0;
for(int i = 1; i <= s1.size() ; i++)
{
for(int j = 1; j <= s2.size(); j++)
{
if(s1[i - 1] == s2[j - 1])
{
//怎么会呢，就差在后面的一个+1上面,只要确定斜对角是相等的即可
dp[i][j] = dp[i - 1][j - 1] + 1;
//这里面就需要对维护的最大值进行更新，以保障得到的用户一直处于最后的位子
if(res <= dp[i][j])
{
res = dp[i][j];
pos = i;//代表最后终止的地方
}
}
//不相等的话直接置零即可
else{
dp[i][j] = 0;
}
}
}
string r;
//截取当前子序列的值，然后处理即可
r.assign(s1.begin() + pos - res , s1.begin() + pos);
std::cout << r << " res = " << res << " pos = " << pos << std::endl;
if(r.size() == 0) return "-1";
return r;
}
};
