最长公共字串（动态规划）-蒲公英云

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

【题目】
给定两个字符串 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;
}