【动态规划】求最长公共子串，最长回文子串

朴灿烈づ我的快乐病毒、 2022-08-09 00:59 201阅读 0赞

题目 : 给定两个字符串，求出它们之间连续的最长的相同子字符串的长度。  
eg : fbaabe，ebaabf，连续最长子串长度为4。

注意：求最长回文子串也可以用求最长公共子串来求，只需将字符串反转作为另外一个字符串，回文部分反转之后不变，然后求LCS（Longest common substring）即可。

求最长公共子串通常两种方法：第一暴力，第二，动态规划。这里分别给出。

## 1. 暴力解法 ##

char* lcs2(char* s1,char* s2)
    {
        int i,j;
        char* shortstr,*longstr;
        char* substr;
        if (NULL == s1 || NULL == s2)
        {
            return NULL;
        }
        if (strlen(s1)<strlen(s2))
        {
            shortstr = s1;
            longstr = s2;
        }
        else
        {
            shortstr = s2;
            longstr = s1;
        }
        if (strstr(longstr,shortstr) != NULL)
        {
            return shortstr;
        }
        substr = (char*)malloc(sizeof(char)*(strlen(shortstr)-1));
        for (i = strlen(shortstr)-1;i>0;i--)
        {
            for(j=0;j < strlen(shortstr);j++)
            {
                memcpy(substr,&shortstr[j],i);
                substr[i] = '\0';
                if (strstr(longstr,substr) != NULL)
                {
                    return substr;
                }
            }
        }
        return NULL;
    }

## 2. 动态规划解 ##

> 求字符串str1,str2的最长公共子串的长度。  
> 定义二元函数函数f(m,n)：分别以str1\[m\],str2\[n\]结尾的连续公共子串的长度  
> 而对于f(m+1,n+1) 有以下种情况：  
> 1.str1\[m+1\] != str2\[n+1\],则有f(m+1,n+1) =0  
> 2.str1\[m+1\] == str2\[n+1\],则有f(m+1,n+1) = f(m,n) + 1  
> 另外，  
> f(0,j) = s1\[0\] == s2\[j\] ? 1:0 where (j>=0)  
> f(i,0) = s1\[i\] == s2\[0\] ? 1:0 where (j>=0)  
> 按照上面这个公式，我们用容易写出这个算法的实现。

void commonstr(char* s1,char* s2)
    {
        int max,i,j,len1,len2,col,row,index;
        row = len1 = strlen(s1);    col = len2 = strlen(s2);
        int *b = (int*)malloc(sizeof(int)*len1*len2);   //二维数组存储以i，j结尾的字符串长度
    #define b(i,j) *(b+(i)*col + j)
        /*memset(b,0,sizeof(int)*len1*len2);*/
        for (i =0;i<len1;i++)   //动归初始条件
        {
            if (s1[i] == s2[0])
                b(i,0) = 1;
            else
                b(i,0) = 0;
        }
        for (j=0;j<len2;j++)
        {
            if (s1[0] == s2[j])
                b(0,j) = 1;
            else
                b(0,j) = 0;
        }
        max = 0;    
        for (i=1;i<len1;i++)
        {
            for (j=1;j<len2;j++)
            {
                if (s1[i] == s2[j])
                {
                    b(i,j) = b(i-1,j-1) + 1;
                    max = b(i,j)>max ? b(i,j):0;
                    index = i+1;
                }
                else
                {
                    b(i,j) = 0;
                }
            }
        }
        char* result = new char[len1+1];
        strncpy(result,&s1[index-max],max);
        result[max] = '\0';
        cout << "最长子串长度：" << max <<endl;
        cout << "最长子串:" << result << endl;
    #undef b
        delete[] b;
        delete[] result;
    }