20最长公共子串
1 问题描述
串1 为 BDCABA
串2 为 ABCBDAB
则两个串的最长公共子串为 BDAB
2 问题解决方法
建立一个矩阵
l[i][j] 表示a串i位置 和 b串j位置，处两者最大的子串数
1 + l[i-1][j-1] 当a[i] == b[j]
l[i][j] =
max(l[i-1][j] , l[i][j-1])
若求 最长的非连续子数组，则DP递归函数为
1 + l[i-1][j-1] 当a[i] == b[j]
l[i][j] =
0 a[i] != b[j]
建立另外一个辅助矩阵，存储移动方向
方向分为斜向上，向左，向右。
3 代码如下：
#include <iostream>
#include <cstring>
using namespace std ;
const int N = 6 ;
const int M = 7 ;
int l[N][M] ;
int p[N][M] ; //存储移动方向
const int LEFT = 1 ;
const int UP = 2 ;
const int ARROW = 3 ;
void lcs(const string & a , const string & b)
{
int i , j ;
for(i = 0 ; i < a.size() ; i++)
{
for(j = 0 ; j < b.size() ; j++)
{
if(i==0 || j == 0)
{
if(a[i] == b[j])
{
l[i][j] = 1;
p[i][j] = ARROW ;
}
else
l[i][j] = 0 ;
continue ;
}
if(a[i] == b[j])
{
l[i][j] = l[i-1][j-1] + 1;
p[i][j] = ARROW ;
}
else
if(l[i][j-1] > l[i-1][j])
{
l[i][j] = l[i][j - 1] ;
p[i][j] = LEFT ;
}
else
{
l[i][j] = l[i - 1][j] ;
p[i][j] = UP;
}
}
}
}
void path(const string & a , int i , int j)
{
if(i >= 0 && j >= 0 )
{
if(p[i][j] == ARROW)
{
path(a , i-1 , j-1) ;
cout<<a[i];
}
else
if(p[i][j] == LEFT)
path(a , i , j - 1 ) ;
else
if(p[i][j] == UP)
path(a , i - 1 , j ) ;
}
}
int main()
{
string s1 = "bdcaba" ;
string s2 = "abcbdab" ;
lcs(s1 , s2) ;
cout<<l[N-1][M-1] ;
path(s1 , N - 1 ,M - 1) ;
system("pause") ;
return 0 ;
}