最长公共子串

秒速五厘米 2021-10-19 05:48 363阅读 0赞

#### 最长公共子串（注意子串是连续的，也是与最长公共子序列的区别） ####

1、先建立一个二维数组array\[str1.size()\]\[str2.size()\]（全部初始化为0），初始化第一行和第一列（元素相同处置1），然后进入状态方程

2、状态转移方程：  
if(str1\[i\] == str2\[i\]) 　　array\[i\]\[j\]=array\[i-1\]\[j-1\]+1;　　（左上方对角线的值加上1）  
　　否则无操作。

3、最后寻找整个array中的最大值即可（因为可能有多个子串）示意（图中有两个公共子串，分别为"ab"和"de"，长度都为2）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3doaWxlMTA_size_16_color_FFFFFF_t_70]  
**代码：**

#include <vector>  
        #include <string>  
        #include <iostream>  
        #include <string.h>  
        #include <sstream>  
        using namespace std;  
          
        int LCS_length(const string &str1, const string &str2, vector<vector<int> > &veca) {  
            int i, j;  
            int biggest = 0;  
            if (str1 == "" || str2 == "")  
                return 0;  
            for (i = 0; i <= str1.length(); i++) {  
                veca[i].resize(str2.length() + 1, 0);  
            }  
            for (j = 0; j <= str2.length(); j++) {  
                veca[0][j] = 0;  
            }  
            for (i = 1; i <= str1.length(); i++) {  
                for (j = 1; j <= str2.length(); j++) {  
                    if (str1[i - 1] == str2[j - 1]) {  
                        veca[i][j] = veca[i - 1][j - 1] + 1;  
                        if (veca[i][j] > biggest)  
                            biggest = veca[i][j];  
                    }  
                    else  
           //可以看出，求最长子串和求最长子序列差别仅仅在这里
                        veca[i][j] = 0;  
                      
                }  
            }  
            return biggest;  
        }  
          
        int main() {  
            string input;  
            getline(cin, input);  
            stringstream ss(input);  
            string str1;  
            ss >> str1;  
            string str2;  
            ss >> str2;  
            vector<vector<int> > veca(str1.length() + 1);  
            cout << LCS_length(str1, str2, veca) << endl;  
            return 0;  
        }

如果想输出串，只需要在`biggest = veca[i][j];`下面加上一句代码保存下标或者j即可，然后根据下标和串的长度即可输出公共子串。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3doaWxlMTA_size_16_color_FFFFFF_t_70]: /images/20211018/dfc312aade804420af4617b682c68a4c.png