算法练习动态规划最长公共子串问题

目录

1.查找两个字符串a,b中的最长公共子串

2.公共子串计算

1.查找两个字符串a,b中的最长公共子串

题目描述：

查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。 注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！

输入描述：输入两个字符串     输出描述：返回重复出现的字符

思路分析：

分析题目，需要找到最长公共字串。关于最长最短问题，一般采用动态规划。

首先我们先明确子串和子序列：

字串是在主字符串中连续的字符串，而子序列是不连续的。

既然知道了是采用动态规划，那么我们下面对问题进行分析：

我们将两个字符串的字符逐一对比，然后将对比的结果（即如果相等，那么在原有的长度基础上加1）保存在数组中。因为要返回子串，因此需要拿到最长子串的起始位置和长度，长度保存在了数组中，起始位置我们通过计算得出来。请看下图：

保存结果的数组为二维数组，全部初始化为0，其列和宽我们将其定义成str1的长度 1和str2的长度 1，以方便计算拿着前面的结果来计算后面的结果。然后对于子串的起始位置start的计算方式是当前行数减去当前最长子串的长度。

定义i和j，i为行、j为列。从1开始，去比较两个字符串中的字符。比较完后，i往下走一步，j返回到1的位置重新遍历并且对比。直至将字符串对比完！

代码如下：

1.  
   #include <iostream>
2.  
   #include<string>
3.  
   #include<vector>
4.  
   #include<algorithm>
5.  
   using namespace std;
6.  
    
7.  
   string LongerStr(string& str1, string& str2)
8.  
   {
9.  
   //默认str1小
10.  
    if (str1.size() > str2.size())
11.  
    {
12.  
    swap(str1, str2);
13.  
    }
14.  
    int n = str1.size();
15.  
    int m = str2.size();
16.  
    int start = 0, max_size = 0;
17.  
    vector<vector<int>> vv(n 1, vector<int>(m 1, 0));
18.  
    for (int i = 1; i <= n; i)
19.  
    {
20.  
    for (int j = 1; j <= m; j)
21.  
    {
22.  
    if (str1[i - 1] == str2[j - 1])
23.  
    {
24.  
    vv[i][j] = vv[i - 1][j - 1] 1;
25.  
    }
26.  
    if (max_size < vv[i][j])
27.  
    {
28.  
    max_size = vv[i][j];
29.  
    start = i - max_size;
30.  
    }
31.  
    }
32.  
    }
33.  
    return str1.substr(start, max_size);
34.  
     
35.  
    }
36.  
     
37.  
    int main() {
38.  
    string str1;
39.  
    string str2;
40.  
    cin >> str1 >> str2;
41.  
    string result = LongerStr(str1, str2);
42.  
    cout << result << endl;
43.  
    }

2.公共子串计算

题目描述：

给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。 注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。

输入描述：输入两个只包含小写字母的字符串 输出描述：输出一个整数，代表最大公共子串的长度

思路分析：

这道题跟上一道是思路完全一样，只不过这道题是输出最长公共子串的长度，而不是输出最长公共子串。因此，可以将上一道题的max_size直接输出即可。

1.  
   #include <iostream>
2.  
   #include<string>
3.  
   #include<vector>
4.  
   #include<algorithm>
5.  
   using namespace std;
6.  
    
7.  
   int LongerStr(string& str1, string& str2)
8.  
   {
9.  
   int n = str1.size();
10.  
    int m = str2.size();
11.  
    int start = 0, max_size = 0;
12.  
    vector<vector<int>> vv(n 1, vector<int>(m 1, 0));
13.  
    for (int i = 1; i <= n; i)
14.  
    {
15.  
    for (int j = 1; j <= m; j)
16.  
    {
17.  
    if (str1[i - 1] == str2[j - 1])
18.  
    {
19.  
    vv[i][j] = vv[i - 1][j - 1] 1;
20.  
    }
21.  
    if (max_size < vv[i][j])
22.  
    {
23.  
    max_size = vv[i][j];
24.  
    }
25.  
    }
26.  
    }
27.  
    return max_size;
28.  
     
29.  
    }
30.  
     
31.  
    int main() {
32.  
    string str1;
33.  
    string str2;
34.  
    cin >> str1 >> str2;
35.  
    int result = LongerStr(str1, str2);
36.  
    cout << result << endl;
37.  
    }

这篇好文章是转载于：学新通技术网