目录
1.查找两个字符串a,b中的最长公共子串
2.公共子串计算
1.查找两个字符串a,b中的最长公共子串
题目描述：
查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。 注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！
输入描述：输入两个字符串 输出描述：返回重复出现的字符
思路分析：
分析题目，需要找到最长公共字串。关于最长最短问题，一般采用动态规划。
首先我们先明确子串和子序列：
字串是在主字符串中连续的字符串，而子序列是不连续的。
既然知道了是采用动态规划，那么我们下面对问题进行分析：
我们将两个字符串的字符逐一对比，然后将对比的结果（即如果相等，那么在原有的长度基础上加1）保存在数组中。因为要返回子串，因此需要拿到最长子串的起始位置和长度，长度保存在了数组中，起始位置我们通过计算得出来。请看下图：
保存结果的数组为二维数组，全部初始化为0，其列和宽我们将其定义成str1的长度 1和str2的长度 1，以方便计算拿着前面的结果来计算后面的结果。然后对于子串的起始位置start的计算方式是当前行数减去当前最长子串的长度。
定义i和j，i为行、j为列。从1开始，去比较两个字符串中的字符。比较完后，i往下走一步，j返回到1的位置重新遍历并且对比。直至将字符串对比完！
代码如下：
代码语言：javascript复制#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
string LongerStr(string& str1, string& str2)
{
//默认str1小
if (str1.size() > str2.size())
{
swap(str1, str2);
}
int n = str1.size();
int m = str2.size();
int start = 0, max_size = 0;
vector<vector<int>> vv(n 1, vector<int>(m 1, 0));
for (int i = 1; i <= n; i)
{
for (int j = 1; j <= m; j)
{
if (str1[i - 1] == str2[j - 1])
{
vv[i][j] = vv[i - 1][j - 1] 1;
}
if (max_size < vv[i][j])
{
max_size = vv[i][j];
start = i - max_size;
}
}
}
return str1.substr(start, max_size);
}
int main() {
string str1;
string str2;
cin >> str1 >> str2;
string result = LongerStr(str1, str2);
cout << result << endl;
}2.公共子串计算
题目描述：
给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。 注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。
输入描述：输入两个只包含小写字母的字符串 输出描述：输出一个整数，代表最大公共子串的长度
思路分析：
这道题跟上一道是思路完全一样，只不过这道题是输出最长公共子串的长度，而不是输出最长公共子串。因此，可以将上一道题的max_size直接输出即可。
代码语言：javascript复制#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int LongerStr(string& str1, string& str2)
{
int n = str1.size();
int m = str2.size();
int start = 0, max_size = 0;
vector<vector<int>> vv(n 1, vector<int>(m 1, 0));
for (int i = 1; i <= n; i)
{
for (int j = 1; j <= m; j)
{
if (str1[i - 1] == str2[j - 1])
{
vv[i][j] = vv[i - 1][j - 1] 1;
}
if (max_size < vv[i][j])
{
max_size = vv[i][j];
}
}
}
return max_size;
}
int main() {
string str1;
string str2;
cin >> str1 >> str2;
int result = LongerStr(str1, str2);
cout << result << endl;
}
