最长公共子串问题

转载自http://blog.csdn.net/steven30832/article/details/8260189

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

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

　　然后重新看一下这个问题，我们建立一个比较矩阵来比较两个字符串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的查找时间。

　　空间上也可以做改进，如果按照如上的方式构造，我们发现，当矩阵的第i+1行的值计算完成后，第i行的值就没有用了，即便是最长的长度出现在第i 行，我们也已经用变量记录下来了。因此，可以将矩阵缩减成一个向量来处理，向量的当前值对应第i行，向量的下一个循环后的值对应第i+1行。

　　该程序为原版转载程序，仍旧有错误，比如忽略了长度相同的情况和当j=0的情况

//    最长公共子串（连续）    LCS
//    Deng Chao
//     2012.12.4

#include <iostream>
#include <cstring>
using namespace std;


//    查找公共子串
//    lcs记录公共子串
//    return    公共子串长度
int LCS(const char *str1  , int len1 , const char *str2 , int len2 , char *&lcs)
{
    if(NULL == str1 || NULL == str2)
    {
        return -1;    //空参数
    }
    
    //    压缩后的最长子串记录向量
    int *c = new int[len2+1];
    for(int i = 0 ; i < len2 ; ++i)
    {
        c[i] = 0;
    }
    int max_len = 0;    //匹配的长度
    int pos = 0;        //在str2上的匹配最末位置
    for(int i = 0 ; i < len1 ; ++i)
    {
        for(int j = len2 ; j > 0 ; --j)    //更新时从后往前遍历  ！！忽略了j=0的情况
        { 
            if(str1[i] == str2[j-1])
            {
                c[j] = c[j-1] + 1;
                if(c[j] > max_len)
                {
                    max_len = c[j];
                    pos = j-1;
                }
            }
            else
            {
                c[j] = 0;
            }
        }
    }
    
    if(0 == max_len)
    {
                delete [] c;
        return 0;
    }
    
    //    得到公共子串
    lcs = new char[max_len];
    for(int i = 0 ; i < max_len ; ++i)
    {
        lcs[i] = str2[pos-max_len+1+i];
    }
    cout<<"pos = "<<pos<<endl;
    delete [] c;
        delete [] lcs;
    return max_len;
    
}

//    test
int main()
{
    const char *str1 = "abacaba";
    const char *str2 = "caba";
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    
    char *lcs;
    
    int len = LCS(str1 , len1 , str2 , len2 , lcs);
    cout<<"max length = "<<len<<endl;
    for(int i = 0 ; i < len ; ++i)
    {
        cout<<lcs[i]<<" ";
    }
}
　　该程序为原版转载程序，仍旧有错误，比如忽略了长度相同的情况和当j=0的情况：

在更新最长子串长度的向量时，是从后往前遍历更新的，若从前往后遍历更新会将向量值覆盖。

Java版本程序： 相同长度问题仍旧未解决！！！

package testcode;
public class Test {
    public static class LCString{
        int maxLen = 0;
        StringBuffer resSb = new StringBuffer();
    }
    
    public static LCString CalLcs(String str1, String str2){
        //定义并初始化返回值
        LCString resLcs = new LCString();
        //定义并初始化查找向量
        int[] res = new int[str1.length()];
        for(int r:res){
            r = 0;
        }
        //记录最大子串的尾巴就可以牵出来所有    
        int pos = 0; 
        
        //更新向量，记录最大子串及大小
        for(int i = 0;i <str2.length();i++){
            //要从后向前更新，否则会将上一行要用到的数据覆盖掉
            for(int j = str1.length() - 1;j >= 0;j--){ 
                if(str2.charAt(i) == str1.charAt(j)){
                    if(j>0){
                        res[j] = res[j-1] + 1;
                        if(res[j] > resLcs.maxLen){// = 的情况怎么办 暂时忽略
                            resLcs.maxLen = res[j];
                            pos = j;
                        }
                    }
                    else
                        res[j] = 1;
                }
                else
                    res[j] = 0;
            }//for inner
        }//for outer
        //构造最大子串
        for(int k = pos - resLcs.maxLen + 1;k <= pos;k++){
            resLcs.resSb.append(str1.charAt(k));
        }        
        return resLcs;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String str1 = "bab";
        String str2 = "caba";
        System.out.println("最大子串长"+CalLcs(str1,str2).maxLen);    
        System.out.println("最大子串:"+CalLcs(str1,str2).resSb.toString());
    }

}

 ---------------------------------

相同长度问题可以通过创建一个栈解决

　　如果当前长度等于resLcs.maxLen则将resLcs.maxLen和pos压栈。等到全部检查完只需弹出栈顶长度跟目前长度比较，如果小于则忽略不计，如果仍旧相同则说明存在相同长度子串，构成子串，并再pop一个继续判断。至于如何返回这么多子串。。。