最长公共子序列|最长公共子串|最长重复子串|最长不重复子串|最长回文子串|最长递增子序列|最大子数组和

参考：http://www.ahathinking.com/archives/124.html

最长公共子序列

1、动态规划解决过程

1）描述一个最长公共子序列

　　如果序列比较短，可以采用蛮力法枚举出X的所有子序列，然后检查是否是Y的子序列，并记录所发现的最长子序列。如果序列比较长，这种方法需要指数级时间，不切实际。

　　LCS的最优子结构定理：设X={x₁，x₂，……，x_m}和Y={y₁，y₂，……，y_n}为两个序列，并设Z={z₁、z₂、……，z_k}为X和Y的任意一个LCS，则：

（1）如果x_m=y_n，那么z_k=x_m=y_n，而且Z_k-1是X_m-1和Y_n-1的一个LCS。

　　（2）如果x_m≠y_n，那么z_k≠x_m蕴含Z是是X_m-1和Y_n的一个LCS。

　　（3）如果x_m≠y_n，那么z_k≠y_n蕴含Z是是X_m和Y_n-1的一个LCS。

　　定理说明两个序列的一个LCS也包含两个序列的前缀的一个LCS，即LCS问题具有最优子结构性质。

2）一个递归解

　　根据LCS的子结构可知，要找序列X和Y的LCS，根据x_m与y_n是否相等进行判断的，如果x_m=y_n则产生一个子问题，否则产生两个子问题。设C[i,j]为序列X_i和Y_j的一个LCS的长度。如果i=0或者j=0，即一个序列的长度为0，则LCS的长度为0。LCS问题的最优子结构的递归式如下所示：

实现算法：

void lcs_length()
{
    int i,j;
    for(i=1;i<=X_LEN;i++)
        c[i][0]=0;
    for(i=0;i<=Y_LEN;i++)
        c[0][i]=0;
    for(i=1;i<=X_LEN;i++)
        for(j=1;j<=Y_LEN;j++)
    {
        if(s1[i-1]==s2[j-1])
        {
            c[i][j]=c[i-1][j-1]+1;
            b[i][j]='\';
        }
        else if(c[i-1][j]>=c[i][j-1])
        {
            c[i][j]=c[i-1][j];
            b[i][j]='|';
        }
        else
        {
            c[i][j]=c[i][j-1];
            b[i][j]='-';
        }
    }
}

最长公共子串

动态规划有一个经典问题是最长公共子序列，但是这里的子序列不要求连续，如果要求序列是连续的，我们叫公共子串，那应该如何得到这个串呢？

最简单的方法就是依次比较，以某个串为母串，然后生成另一个串的所有长度的子串，依次去母串中比较查找，这里可以采用先从最长的子串开始，减少比较次数，但是复杂度依然很高！

然后重新看一下这个问题，我们建立一个比较矩阵来比较两个字符串str1和str2

定义 lcs(i,j) ，当str1[i] = str2[j]时lcs(i,j)=1,否则等于0。

example:

str1 = "bab"

str2 = "caba"

建立矩阵

--b a b

c 0 0 0

a 0 1 0

b 1 0 1

a 0 1 0

连续i子串的特点就是如果str1[i]和str2[j]是属于某公共子串的最后一个字符，那么一定有str1[i]=str2[j] && str1[i-1] = str2[j-1]，从矩阵中直观的看，就是由“1”构成的“斜线”代表的序列都是公共子串，那么最长公共子串肯定就是斜线“1”最长的那个串。

那么现在问题就可以转化了，只要构造出如上的一个矩阵，用n^2的时间就可以得到矩阵，然后再到矩阵中去寻找最长的那个“1”构成的斜线就可以了！那么，现在又有了新的问题？如何快速的找到那个“1”构成的最长斜线呢？

采用DP的思想，如果str1[i] = str2[j]，那么此处的包含str1[i] 和 str2[j]公共子串的长度必然是包含str1[i-1]和str2[j-1]的公共子串的长度加1，那么现在我们可以重新定义lcs(i,j)，即是lcs(i,j) = lcs(i-1,j-1) + 1，反之，lcs(i,j) = 0。那么上面的矩阵就变成了如下的样子：

--b a b

c 0 0 0

a 0 1 0

b 1 0 2

a 0 2 0

现在问题又变简单了，只需要花n^2的时间构造这样一个矩阵，再花n^2的时间去找到矩阵中最大的那个值，对应的就是最长公共子串的长度，而最大值对应的位置对应的字符，就是最长公共子串的最末字符。

算法还可以改进，我们可以将查找最大长度和对应字符的工作放在构造矩阵的过程中完成，一边构造一边记录当前的最大长度和对应位置，这样就节省了n^2的查找时间。

实现算法：

/* 最长公共子串 DP */
int dp[30][30];
 
void LCS_dp(char * X, int xlen, char * Y, int ylen)
{
    maxlen = maxindex = 0;
    for(int i = 0; i < xlen; ++i)
    {
        for(int j = 0; j < ylen; ++j)
        {
            if(X[i] == Y[j])
            {
                if(i && j) //i和j都不为0的时候
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                if(i == 0 || j == 0)
                {
                    dp[i][j] = 1;
                }
                if(dp[i][j] > maxlen)
                {
                    maxlen = dp[i][j]; //最长的子串长度
                    maxindex = i + 1 - maxlen;//求出公共子串开始的位置
                }
            }
        }
    }
    outputLCS(X);
}

最长重复子串

问题描述
给定一个字符串，求出其最长重复子串
例如：abcdabcd
最长重复子串是 abcd，最长重复子串可以重叠
例如：abcdabcda，这时最长重复子串是 abcda，中间的 a 是被重叠的。

直观的解法是，首先检测长度为 n - 1 的字符串情况，如果不存在重复则检测 n - 2, 一直递减下去，直到 1 。
这种方法的时间复杂度是 O(N * N * N)，其中包括三部分，长度纬度、根据长度检测的字符串数目、字符串检测。

一种是暴力解决的方法：

int comlen(const char *a,const char *)
{
    if(a==NULL||b==NULL)
        return 0;
    int i=0;
    while(a[i]!='

最长公共子序列|最长公共子串|最长重复子串|最长不重复子串|最长回文子串|最长递增子序列|最大子数组和

参考：http://www.ahathinking.com/archives/124.html