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 ;
}