alg-最长公共子串
2024-09-07 08:36:23
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;
}
};
最新文章
- linux下php-mysql拓展安装
- vs快捷键大全
- CFNetwork的错误代码参考
- db2数组、函数
- JS实现设为首页与加入收藏
- SQL Server 2012 各版本功能比较
- Bmob用户管理操作
- IntelliJ IDEA 15 显示工具栏及底部周边工具栏
- iOS多线程的初步研究(八)-- dispatch队列
- ZooKeeper编程指导
- 对于Java泛型的理解
- android studio友盟分享
- Java 线程池(ThreadPoolExecutor)原理分析与使用
- laravel5.5 任务调度 (转载)
- drf 多表
- Error creating bean with name &#39;student&#39;: Unsatisfied dependency expressed through field &#39;teacher&#39;; nested exception is org.springframework.beans.factory.UnsatisfiedDependencyException: Error creating
- iOS ibeacon 使用详解
- linux 保留文件 其余删除
- mysql常用赋权命令
- Spark RDD Transformation 简单用例(二)