class Solution {
public:
const std::vector<std::string> LongestCommonSubstring(const std::string& s1, const std::string& s2) {
if (s1.empty() || s2.empty()) {
return std::vector<std::string>();
}
//dp
std::vector<std::vector<int>> dp(s1.size()+1,std::vector<int>(s2.size()+1,0));
int max_len=-1;
for(int i=1;i<s1.size()+1;i++) {
for(int j=1;j<s2.size()+1;j++) {
dp[i][j]=(s1[i-1]==s2[j-1])?dp[i-1][j-1]+1:0;
if(dp[i][j]>max_len) {
max_len=dp[i][j];
}
}
}
//print result
std::vector<std::string> res;
for(int i=1;i<s1.size()+1;i++) {
for(int j=1;j<s2.size()+1;j++) {
if(dp[i][j]==max_len) {
res.push_back(s1.substr(i-max_len,max_len));
}
}
}
return res;
}
};
转载于:https://www.cnblogs.com/smallredness/p/11234069.html
相关资源：JAVA上百实例源码以及开源项目
