最长公共字串（动态规划）

落日映苍穹つ 2022-08-18 02:19 140阅读 0赞

【题目】  
给定两个字符串  str1 和  str2，返回两个字符串的最长公共子串。  
【举例】  
str1 =“1AD12345CD ”， str2 =“12345EF”。返回“12345”。  
【要求】  
如果str1 长度为M， str2长度为N，实现时间复杂度为O(M\*N)，额外空间复杂度

为O(1)的方法。

代码实现：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    
    using namespace std;
    
    /*  经典的动态规划，利用dp[i][j]空间复杂度为O(M*N)，还可以进行优化
        因为dp[i][j]只和dp[i-1][j-1]有关，所以可以按照斜线方向来计算，s
        只需要一个变量就可以计算出所有位置的值
    */
    char* getSubList(const char* str1, const char* str2)
    {
        if (str1 == NULL || str2 == NULL)
        {
            return NULL;
        }
    
        int rows = 0; //斜线开始位置的行
        int cols = strlen(str2) - 1; //斜线开始位置的列
    
        int maxlen = 0; //记录最大长度
        int ends = 0; //最大长度更新的时候，记录字串结束的位置
    
        int i = 0, j = 0, len = 0;
        char* pres = NULL;
    
        while(rows < strlen(str1))
        {
            /* 开始进行斜线往下求值 */
            i = rows;
            j = cols;
            len = 0;
    
            /* 边界条件 */
            while(i < strlen(str1) && j < strlen(str2))
            {
                if (str1[i] != str2[j])
                {
                    len = 0;
                }
                else
                {
                    len++;
                }
    
                /* 记录最大值 */
                if (len > maxlen)
                {
                    ends = i;
                    maxlen = len;
                }
    
                i++;
                j++;
            }
    
            if(cols > 0) //斜线开始位置列先向左移动
            {
                cols--;
            }
            else//列移动到最左之后，行往下移动
            {
                rows++;
            }
        }
    
        pres = new char[maxlen+1];
        memcpy(pres,str1+ends-maxlen+1,maxlen);
        pres[maxlen] = '\0';
    
        return pres;
    }
    
    int main()
    {
        char str1[] = "1AD12345CD";
        char str2[] = "12345EF";
    
        cout << getSubList(str1,str2) << endl;
    }