ダイナミックプランニングのLCS
3270 ワード
/**
*動的計画の最長共通サブシーケンス問題:サブシーケンスX=,もう一つのサブシーケンスZ=はXのサブシーケンスであり、Xの厳密なインクリメントダウンシーケンスが存在する場合
*は、すべてのj=1,2に対して、...k,xij=zjがある.Z=がX=サブシーケンスのように、下付きi=<2,3,5,7>
*LCS問題:所与のシーケンスX=とY=,XとYの最長共通サブシーケンスを探し出す
*Zは、XおよびYのいずれかの最長共通サブシーケンスであり、次のようになる.
*1)xn=ymであればzk=xn=ymでありはXn-1とYm-1の最長共通サブシーケンスである
*2)もしxn!=ymはzk!=xnはZを含んでXn-1とYの1つのLCSです
*3)若ym!=xnはzk!=ymはZを含んでxとYm-1の1つのLCSです
*
*上記の結論に基づいて、再帰的な解を得ることができます.
*定義c[i][j]は、シーケンスXiおよびYjのLCSの長さ則である.
*-->0 if i=0またはj=0
*c[i][j]=-->c[i-1][j-1]+1 i>0、j>0、xi=yj
*-->max{c[i-1][j],c[i][j-1]}i>0,j>0,xi!=yj
* @author song
*
*/
/**
テストコード:
result:The longest LCS:[0, 1, 0, 1, 0, 1]
*動的計画の最長共通サブシーケンス問題:サブシーケンスX=
*
*LCS問題:所与のシーケンスX=
*Z
*1)xn=ymであればzk=xn=ymであり
*2)もしxn!=ymはzk!=xnはZを含んでXn-1とYの1つのLCSです
*3)若ym!=xnはzk!=ymはZを含んでxとYm-1の1つのLCSです
*
*上記の結論に基づいて、再帰的な解を得ることができます.
*定義c[i][j]は、シーケンスXiおよびYjのLCSの長さ則である.
*-->0 if i=0またはj=0
*c[i][j]=-->c[i-1][j-1]+1 i>0、j>0、xi=yj
*-->max{c[i-1][j],c[i][j-1]}i>0,j>0,xi!=yj
* @author song
*
*/
/**
* x y
* @param x
* @param y
* @return
*/
public static int[][] calculateCommonSubsequenceNum(char[] x, char[] y){
int n = x.length;
int m = y.length;
// LCS
int[][] c = new int[n+1][m+1];
// ：c[i][j] = 0 i=0 or j=0
for(int i = 0; i <= m; ++i)
c[0][i] = 0;
for(int j = 0; j <= n; ++j)
c[j][0] = 0;
// c[1][1] x[0] y[0] ， x y x[1] y[1]， x[0] y[0]
for( int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if( x[i-1] == y[j-1] )
c[i][j] = c[i-1][j-1] + 1;
else{
c[i][j] = Math.max(c[i-1][j], c[i][j-1]);
}
}
}
return c;
}/**
*
* LCS {@link #calculateCommonSubsequenceNum(char[], char[])} LCS
*
* 1） Z X Y LCS， xn=ym， zk = xn = ym X Y LCS
* 2） xn != ym， Z Xn-1 Ym LCS Xn Ym-1 LCS ， xn!=ym ， Xn-1 Ym LCS/ Xn Ym-1 LCS
* ， c[n-1][m] > c[n][m-1], Xn-1 Ym LCS ， ， Xn Ym-1 LCS
* ， x y ， LCS，
* ， c[n-1][m] > c[n][m-1]， xn-1 ym xn ym-1
*
* @param x
* @param y
* @return
*/
public static List<Character> findLongestLCS(char[] x,char[] y){
List<Character> result = new LinkedList<Character>();
int c[][] = calculateCommonSubsequenceNum(x, y);
int n = x.length - 1;
int m = y.length - 1;
while( n >= 0 && m >= 0){
if(x[n] == y[m]){
result.add(0, x[n]);
n--;m--;
}else{
if(c[n][m+1] > c[n+1][m])
n--;
else
m--;
}
}
return result;
}テストコード:
public static void main(String[] args) {
char[] x = "10010101".toCharArray();
char[] y = "010110110".toCharArray();
List<Character> r = findLongestLCS(x, y);
System.out.println("The longest LCS:" + r.toString());
}result:The longest LCS:[0, 1, 0, 1, 0, 1]