题解 | #NC92-最长公共子串#
最长公共子串
http://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac
class Solution {
public:
/**
* longest common substring
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
// write code here
vector<vector<int>> maxLen(s1.size() + 1, vector<int>(s2.size() + 1, 0)); // 增加外圈0，方便讨论边界
int str_len = 0, str_end_idx = 0; // 记录最长子串长度及结束index
for (int i = 0; i < s1.size(); i++)
for (int j = 0; j < s2.size(); j++) {
if (s1[i] == s2[j]) {
maxLen[i + 1][j + 1] = maxLen[i][j] + 1;
if (maxLen[i + 1][j + 1] > str_len) {
str_len++;
str_end_idx = i;
} // 当有很多个子串时，找最长的那个
}
else
maxLen[i + 1][j + 1] = 0; // 构建最小公共子串的长度矩阵，0表示该元素不在子串内
}
// for (int i = 0; i < s1.size(); i++) {
// for (int j = 0; j < s2.size(); j++)
// cout << maxLen[i + 1][j + 1] << " ";
// cout << endl;
// }
return s1.substr(str_end_idx - str_len + 1, str_len);
}
}; 
