【动态规划】最长公共子串问题

newer · 发表于 2014-11-29 09:55:15

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

本帖最后由 newer 于 2014-11-29 09:59 编辑

  1、问题相关定义：
      (1)字符串:一个字符串S是将n 个字符顺次排列形成的数组, n称为S的长度,表示为len(S) 。S的第i字符表示为S[ i ]。
   (2)子串:字符串S的子串S[ i:j ] ( i ≤ j)表示S串中从i到j这一段,也就是排列S[ i ] , S[ i + 1 ] , …,S[ j ] 形成的字符串。
   (3)后缀:后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串S的从i开头的后缀表示为Suffix( S,i) ,也就是Suffix( S, i) = S[ i:len ( S) ]。
   (4)公共后缀:字符串U 如果既是字符串S的后缀又是字符串T的后缀,则字符串U 是字符串S和T的一个公共后缀。
   (5)最长公共后缀:字符串S和T的最长公共后缀是指字符串S和T的所有公共后缀中长度最大的子串。
   (4)公共子串：字符串U 如果既是字符串S的子串又是字符串T的子串,则字符串U 是字符串S和T的一个公共子串。
   (5)最长公共子串:字符串S和T的最长公共子串是指字符串S和T的所有公共子串中长度最大的子串。
   例：给定2 个长度分别为4, 4 的字符串“abab”,“baba”,它们的公共子串(Common Substring) 有“”,“a”,“b”,“ab”,“ba”,“aba”,“bab”。其中最长公共子串(LCS) 即为“aba”或“bab”。
      2、动态规划求解
   在使用动态规划求解2个长度分别为p, q的字符串S,T的最长公共子串问题前,先给出求它们任意前缀子串对S[1:i],T[1:j]的最长公共后缀的算法，其中:1 ≤ i ≤ p,1 ≤ j ≤ q。设LCSuffix(S[1:i],T[1:j])表示前缀子串对S[1: i] ,T[1:j] 的最长公共后缀，则该问题的递推关系式如下：

例如:字符串S“baba”, T“abab”, 使用上面递推关系式求得字符串S, T所有前缀子串对的最长公共后缀,如下表所示：

字符串S, T所有前缀子串对应的最长公共后缀中长度最大的即为字符串S, T的最长公共子串,即:

其中LCS( S,T) 表示字符串S, T的最长公共子串。对于字符串S“baba”, T“abab”,从表1中可以看出它们的最长公共后缀中长度最大为3,对应两个最长公共子串,即:"aba"和"bab"。

// CPPPRO.cpp : 定义控制台应用程序的入口点。
//3m6 最长公共子串，动态规划实现
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
string getLCSLength(string &s, string &t);
int main()
{
string s,t;
cout<<"请输入字符串s:"<<endl;
cin>>s;
cout<<"请输入字符串t:"<<endl;
cin>>t;
cout<<"最长公共子串为:"<<endl;
cout<<getLCSLength(s,t)<<endl;
return 0;
}
string getLCSLength(string &s, string &t)
{
int p = s.length();
int q = t.length();
string **num = new string *[p];
for(int i=0;i<p;i++)
{
num = new string[q];
}
char char1 = '\0';
char char2 = '\0';
int len = 0;
string lcs = "" ;
for(int i=0; i<p; i++)
{
for (int j=0; j<t.length(); j++)
{
char1 = s.at(i);
char2 = t.at(j);
if(char1!=char2)
{
num[j] = "" ;
}
else
{
if (i==0||j==0)
{
num[j]=char1;
}
else
{
num[j]=num[i-1][j-1]+char1;
}
if(num[j].length()>len)
{
len = num[j].length() ;
lcs = num[j];
}
else if(num[j].length()==len)
{
lcs = lcs + "," + num[j];
}
}
}
}
for(int i=0;i<p;i++)
{
delete[] num;
}
delete[] num;
return lcs;
}

// CPPPRO.cpp : 定义控制台应用程序的入口点。 
//3m6 最长公共子串，动态规划实现 
#include "stdafx.h" 
#include <iostream>   
#include <string> 
using namespace std; 
 
string getLCSLength(string &s, string &t); 
 
int main() 
{ 
        string s,t; 
        cout<<"请输入字符串s:"<<endl; 
        cin>>s; 
        cout<<"请输入字符串t:"<<endl; 
        cin>>t; 
        cout<<"最长公共子串为:"<<endl; 
        cout<<getLCSLength(s,t)<<endl; 
        return 0; 
} 
 
string getLCSLength(string &s, string &t) 
{ 
        int p = s.length(); 
        int q = t.length(); 
 
        string **num = new string *[p];   
    for(int i=0;i<p;i++)    
    {    
        num = new string[q];   
    }    
 
        char char1 = '\0'; 
        char char2 = '\0'; 
 
        int len = 0; 
        string lcs = "" ; 
 
        for(int i=0; i<p; i++) 
        { 
                for (int j=0; j<t.length(); j++) 
                { 
                        char1 = s.at(i); 
                        char2 = t.at(j); 
                        if(char1!=char2) 
                        { 
                                num[j] = "" ; 
                        } 
                        else 
                        { 
                                if (i==0||j==0) 
                                { 
                                        num[j]=char1; 
                                } 
                                else 
                                { 
                                        num[j]=num[i-1][j-1]+char1; 
                                } 
                                if(num[j].length()>len) 
                                { 
                                        len = num[j].length() ; 
                                        lcs = num[j]; 
                                } 
                                else if(num[j].length()==len) 
                                { 
                                        lcs = lcs + "," + num[j]; 
                                } 
                        } 
                } 
        } 
 
        for(int i=0;i<p;i++)    
    {    
        delete[] num; 
    } 
        delete[] num; 
 
        return lcs; 
}

程序运行结果如下：

 使用动态规划算法求2个长度分别为p, q的字符串S, T的最长公共子串需要构造一个二维表,该二维表含有pq个项,使用递推的方法求每项的时间负责度为O (1) ,所以求出所有项的时间复杂度为O (pq) 。在二维表中只需找到一个最大值项,其对应于原2个字符串的最长公共子串,因此使用动态规划算法的时间复杂度为O (pq) 。
 建立2个长度分别为p, q的字符串S, T的广义后缀数组的时间复杂度为O (p + q) ,求广义后缀数组中相邻子串的最长公共前缀的时间复杂度为<O(p + q) ,O(1)>,即需要预处理时间复杂度为O(p + q) ,每次查询最长公共前缀的时间复杂度为O(1) 。遍历所有最长公共前缀的时间复杂度为O(p+q) ,因此使用广义后缀数组解决最长公共子串的时间复杂度为O(p+q) 。对于字符串S, T,它的广义后缀数组在不降低性能同时需要使用2 (p + q) 空间。
 解决2个长度分别为p, q的字符串最长公共子串问题的动态规划算法,广义后缀树算法以及广义后缀数组算法在时间复杂度,空间复杂度以及编程实现上的比较分析总结如下表所示：

 其中动态规划算法以及广义后缀树算法的研究已经非常成熟,在计算机算法领域有着各种各样的应用,但在解决字符串最长公共子串问题上还有一定不足,即动态规划算法占用的时间复杂度以及空间复杂度都很高,而广义后缀树算法虽然降低了时间复杂度,但其空间复杂度还是较高,另外编程实现也较难。虽然广义后缀数组的理论研究还在发展中,但就目前的研究成果而言,在解决字符串最长公共子串问题上,根据上面给出的算法,它可以综合动态规划算法以及广义后缀树算法的优点,既保证了线性的时间复杂度,较低的空间复杂度又易于编程实现。改进的后缀数组算法及相关定义应用可查看博文《最长公共子串问题的后缀数组解法》。

newer · 发表于 2014-11-29 10:01:09

/*
35、编程实现：找出两个字符串中最大公共子字符串,如"abccade","dgcadde"的最大子串为
"cad"
不同于56的最长公共子串
DP题算法导论上有：
c[i,j]=0 i=0||j=0
=c[i-1,j-1]+1 a==a[j]
=max(c[i-1,j],c[i,j-1]) a!=a[j]
本题就是循环枚举
*/
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;
int GetCommon(char s1[], char s2[])
{
int len1=strlen(s1);
int len2=strlen(s2);
int r,maxlen=0;
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
if(s1==s2[j])
{
int as=i,bs=j,count=1;
while(as+1<len1&&bs+1<len2 &&s1[++as]==s2[++bs])
count++;
if(count>maxlen)
{
maxlen = count;
r=i;
}
}
}
}
for(int i=r;i<r+maxlen;i++)
printf("%c",s1);
printf("\n");
return maxlen;
}
int main()
{
char a[]={"abccade"};
char b[]={"dgcadde"};
printf("%s和%s的最长公共子串是：\n",a,b);
printf("长度为：%d\n",GetCommon(a,b));
return 0;
}

/* 
35、编程实现：找出两个字符串中最大公共子字符串,如"abccade","dgcadde"的最大子串为 
"cad" 
 
不同于56的最长公共子串 
DP题算法导论上有： 
c[i,j]=0                      i=0||j=0 
          =c[i-1,j-1]+1           a==a[j] 
          =max(c[i-1,j],c[i,j-1]) a!=a[j]        
 
本题 就是循环枚举 
*/ 
 
#include<iostream> 
#include<stdio.h> 
#include<cmath> 
#include<algorithm> 
using namespace std; 
 
int GetCommon(char s1[], char s2[]) 
{ 
        int len1=strlen(s1); 
        int len2=strlen(s2); 
        int r,maxlen=0; 
        
        for(int i=0;i<len1;i++) 
        { 
                for(int j=0;j<len2;j++) 
                { 
                        if(s1==s2[j]) 
                        { 
                                int as=i,bs=j,count=1; 
                                while(as+1<len1&&bs+1<len2 &&s1[++as]==s2[++bs]) 
                                        count++; 
                                if(count>maxlen) 
                                { 
                                        maxlen = count; 
                                        r=i; 
                                } 
                        } 
                } 
        } 
        for(int i=r;i<r+maxlen;i++) 
                printf("%c",s1); 
        printf("\n"); 
        return maxlen; 
} 
int main() 
{ 
        char a[]={"abccade"}; 
        char b[]={"dgcadde"}; 
        printf("%s和%s的最长公共子串是：\n",a,b); 
        printf("长度为：%d\n",GetCommon(a,b)); 
        
        return 0; 
}

newer · 发表于 2014-11-29 10:14:44

//获取两个字符串公共子串
int GetMaxCommonSubStr(string &strFirst, string &strSecond)
{
if((strFirst=="") || (strSecond==""))
{
return 0;
}
int i, j;
int iLenFirst = strFirst.length();
int iLenSecond = strSecond.length();
int iMaxCmnLne = 0; //最大公共子串长度
string strLCS = ""; //存储最大公共子串
char chFirst, chSecond;
string **num = new string *[iLenFirst];
assert(num!=NULL);
for(i=0; i<iLenFirst; i++)
{
num = new string[iLenSecond];
}
chFirst = '\0';
chSecond = '\0';
for(i=0; i<iLenFirst; i++)
{
chFirst = strFirst.at(i);
for(j=0; j<iLenSecond; j++)
{
chSecond = strSecond.at(j);
if(chFirst != chSecond)
{
num[j] ="";
}
else
{
if(0==i || 0==j)
{
num[j] = chFirst;
}
else
{
num[j] = num[i-1][j-1] + chFirst;
}
if(num[j].length()>iMaxCmnLne) //如果当前获得的最大公共子串比以前的最大的大，则更新最大公共子串长度
{
strLCS = ""; //有新的最大公共子串，以前的作废
iMaxCmnLne = num[j].length();
strLCS = num[j];
}
else if(num[j].length()==iMaxCmnLne) //获取到目前为止多个当前最大公共子串，用，分得开
{
strLCS += ',' + num[j];
}
}
}
}
//内存回收
for(i=0; i<iLenFirst; i++)
{
delete [] num;
}
delete [] num;
return iMaxCmnLne;
}
int _tmain(int argc, _TCHAR* argv[])
{
int iResultLen;
string strLine, InputStr1, InputStr2;
getline(cin, strLine);
istringstream stream(strLine);
stream>>InputStr1;
stream>>InputStr2;
iResultLen = GetMaxCommonSubStr(InputStr1, InputStr2);
cout<<iResultLen;
Sleep(5000);
return 0;
}

//获取两个字符串公共子串 
int GetMaxCommonSubStr(string &strFirst, string &strSecond) 
{ 
        if((strFirst=="") || (strSecond=="")) 
        { 
                return 0; 
        } 
        int i, j; 
        int iLenFirst = strFirst.length(); 
        int iLenSecond = strSecond.length(); 
        int iMaxCmnLne = 0; //最大公共子串长度 
        string strLCS = "";      //存储最大公共子串 
        char chFirst, chSecond; 
        string **num = new string *[iLenFirst]; 
 
        assert(num!=NULL); 
 
        for(i=0; i<iLenFirst; i++) 
        { 
                num = new string[iLenSecond]; 
        } 
 
        chFirst = '\0'; 
        chSecond = '\0'; 
 
        for(i=0; i<iLenFirst; i++) 
        { 
                chFirst = strFirst.at(i); 
                for(j=0; j<iLenSecond; j++) 
                { 
                        chSecond = strSecond.at(j); 
                        if(chFirst != chSecond) 
                        { 
                                num[j] =""; 
                        } 
                        else 
                        { 
                                if(0==i || 0==j) 
                                { 
                                        num[j] = chFirst; 
                                } 
                                else 
                                { 
                                        num[j] = num[i-1][j-1] + chFirst; 
                                } 
 
                                if(num[j].length()>iMaxCmnLne) //如果当前获得的最大公共子串比以前的最大的大，则更新最大公共子串长度 
                                { 
                                        strLCS = "";  //有新的最大公共子串，以前的作废 
                                        iMaxCmnLne = num[j].length(); 
                                        strLCS = num[j]; 
                                } 
                                else if(num[j].length()==iMaxCmnLne) //获取到目前为止多个当前最大公共子串，用，分得开 
                                { 
                                        strLCS += ',' + num[j]; 
                                } 
 
 
                        } 
 
                } 
        } 
 
        //内存回收 
        for(i=0; i<iLenFirst; i++) 
        { 
                delete [] num; 
        } 
        delete [] num; 
 
        return iMaxCmnLne; 
} 
 
 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
 
        int iResultLen; 
        string strLine, InputStr1, InputStr2; 
        getline(cin, strLine); 
 
        istringstream stream(strLine); 
        stream>>InputStr1; 
        stream>>InputStr2; 
 
        iResultLen = GetMaxCommonSubStr(InputStr1, InputStr2);        
        cout<<iResultLen; 
        Sleep(5000); 
 
        return 0; 
}

账号		自动登录	找回密码
密码			立即注册

[分享] 【动态规划】最长公共子串问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。