最长公共子串的问题（正常方法和矩阵法，动态规划）

题目：

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

看法：

这个题我本人看着在网上没有详细的解释，其实你要搞懂一个问题，整体是让你求最长公共子串的长度比较简单，一直双重遍历，比较 最长子串的长度，但是如果最后要你那个最长公共子串难度会有一个提升，

首先下面第一种方法我用双重遍历去找一下，找到最长公共子串，找到最长公共子串的关键是用map去储存字符串，这样以len为键一下就找到了最长公共子串

代码如下：

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int main() {string  s1, s2;s1 = "abcdkkk";s2 = "baabcdadabc";map<int, string>hash;string cnts;int maxlen=0;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改为map<int,vector<string>>，改变 了一下储存方式

代码如下：

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
int main() {string  s1, s2;s1 = "abcdkkk";s2 = "baabcdadabc";map<int, vector<string>>hash;string cnts;int maxlen=0;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(i=1; i<=len1; i++){for(j=1; j<=len2; 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;
}