网站联系我们 怎么做地图,宁波单页面seo,青岛网站制作公司,合伙建网站题目#xff1a;
给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 #xff0c;返回 0 。
一个字符串的 子序列 是指这样一个新的字符串#xff1a;它是由原字符串在不改变字符的相对顺序的情况下删除某些字符…题目
给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。
一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。
例如ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。 看法
这个题我本人看着在网上没有详细的解释其实你要搞懂一个问题整体是让你求最长公共子串的长度比较简单一直双重遍历比较 最长子串的长度但是如果最后要你那个最长公共子串难度会有一个提升
首先下面第一种方法我用双重遍历去找一下找到最长公共子串找到最长公共子串的关键是用map去储存字符串这样以len为键一下就找到了最长公共子串
代码如下
#includeiostream
#includealgorithm
#includemap
using namespace std;
int main() {string s1, s2;s1 abcdkkk;s2 baabcdadabc;mapint, stringhash;string cnts;int maxlen0;int len;int i, j;//双层遍历for循环,只动一个字符串for (i 0; i s1.length(); i) {string s3 ;for (j i; j s1.length(); j) {s3 s1[j];if (s2.find(s3) ! -1) {cnts s3;len s3.length();hash[len] cnts;}}maxlen max(maxlen, len);}cout maxlen hash[maxlen];
}
注意点 如果最大公共子串不止一个将map改为mapint,vectorstring改变 了一下储存方式
代码如下
#includeiostream
#includealgorithm
#includemap
#includevector
using namespace std;
int main() {string s1, s2;s1 abcdkkk;s2 baabcdadabc;mapint, vectorstringhash;string cnts;int maxlen0;int len;int i, j;//双层遍历for循环,只动一个字符串for (i 0; i s1.length(); i) {string s3 ;for (j i; j s1.length(); j) {s3 s1[j];if (s2.find(s3) ! -1) {cnts s3;len s3.length();hash[len].push_back(cnts);}}maxlen max(maxlen, len);}cout maxlen ;for (auto s : hash[maxlen]) {cout s;}
}
矩阵法简单的动态规划
1.把两个字符串组成行和列的二维矩阵
2.如果相同则为值取1不同则取0
3.、通过查找出值为1的最长对角线就能找到最长公共子串 代码如下
int f(const char* s1, const char* s2)
{int a[N][N];int len1 strlen(s1);int len2 strlen(s2);int i,j;memset(a,0,sizeof(int)*N*N);int max 0;for(i1; ilen1; i){for(j1; jlen2; j){if(s1[i-1]s2[j-1]) {a[i][j] a[i-1][j-1]1? a[i-1][j-1]1:1; if(a[i][j] max) max a[i][j];}}}return max;
}
