最長子串（動态規劃）

題目：如果字元串一的所有字元按其在字元串中的順序出現在另外一個字元串二中，

則字元串一稱之為字元串二的子串。

注意，并不要求子串（字元串一）的字元必須連續出現在字元串二中。

請編寫一個函數，輸入兩個字元串，求它們的最長公共子串，并列印出最長公共子串。

例如：輸入兩個字元串BDCABA和ABCBDAB，字元串BCBA和BDAB都是是它們的最長公共子串，

則輸出它們的長度4，并列印任意一個子串。

分析：求最長公共子串（Longest CommonSubsequence, LCS）是一道非常經典的動态規劃題。

以下分析參見另外的一篇博文。

步驟一、描述一個最長公共子序列

先介紹LCS問題的性質：記Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}為兩個字元串，

并設Zk={z0,z1,…zk-1}是X和Y的任意一個LCS，則可得出3條性質：

1.      如果xm-1=yn-1，那麼zk-1=xm-1=yn-1，并且Zk-1是Xm-1和Yn-1的一個LCS；

2.      如果xm-1≠yn-1，那麼當zk-1≠xm-1時，Z是Xm-1和Y的LCS；

3.      如果xm-1≠yn-1，那麼當zk-1≠yn-1時，Z是X和Yn-1的LCS；

下面簡單證明一下由上述相應條件得出的這些性質：

1.      如果zk-1≠xm-1，那麼我們可以把xm-1（yn-1）加到Z中得到Z’，這樣就得到X和Y的一個長度為k+1的公共子串Z’。

這就與長度為k的Z是X和Y的LCS相沖突了。是以一定有zk-1=xm-1=yn-1。

既然zk-1=xm-1=yn-1，那如果我們删除zk-1（xm-1、yn-1）得到的Zk-1，Xm-1和Yn-1，顯然Zk-1是Xm-1和Yn-1的一個公共子串，現在我們證明Zk-1是Xm-1和Yn-1的LCS。用反證法不難證明。假設有Xm-1和Yn-1有一個長度超過k-1的公共子串W，那麼我們把加到W中得到W’，那W’就是X和Y的公共子串，并且長度超過k，這就和已知條件相沖突了。

2.      還是用反證法證明。假設Z不是Xm-1和Y的LCS，則存在一個長度超過k的W是Xm-1和Y的LCS，那W肯定也X和Y的公共子串，而已知條件中X和Y的公共子串的最大長度為k。沖突。

3.      證明同2。

步驟二、一個遞歸解

根據上面的性質，我們可以得出如下的思路：

求兩字元串Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}的LCS，

如果xm-1=yn-1，那麼隻需求得Xm-1和Yn-1的LCS，并在其後添加xm-1（yn-1）即可（上述性質1）；

如果xm-1≠yn-1，我們分别求得Xm-1和Y的LCS和Yn-1和X的LCS，并且這兩個LCS中較長的一個為X和Y的LCS（上述性質2、3）。

根據上述結論，可得到以下公式，

如果我們記字元串Xi和Yj的LCS的長度為c[i,j]，我們可以遞歸地求c[i,j]：

          /     0                              if i<0 or j<0

c[i,j]=         c[i-1,j-1]+1                   if i,j>=0 and xi=xj

        /      max(c[i,j-1],c[i-1,j]          if i,j>=0 and xi≠xj

上面的公式用遞歸函數不難求得。自然想到Fibonacci第n項(本微軟等100題系列V0.1版第19題）問題的求解中可知，

直接遞歸會有很多重複計算，是以，我們用從底向上循環求解的思路效率更高。

為了能夠采用循環求解的思路，我們用一個矩陣（參考下文文末代碼中的LCS_length）儲存下來目前已經計算好了的c[i,j]，

當後面的計算需要這些資料時就可以直接從矩陣讀取。

另外，求取c[i,j]可以從c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三個方向計算得到，

相當于在矩陣LCS_length中是從c[i-1,j-1]，c[i,j-1]或者c[i-1,j]的某一個各自移動到c[i,j]，

是以在矩陣中有三種不同的移動方向：向左、向上和向左上方，其中隻有向左上方移動時才表明找到LCS中的一個字元。

于是我們需要用另外一個矩陣（參考下文文末代碼中的LCS_direction）儲存移動的方向。

然後下面也是參見其博文後，修改部分所得到的C++實作源碼：

// 動态規劃_最大子串.cpp : 定義控制台應用程式的入口點。
//

#include "stdafx.h"
#include<string>
#include<iostream>
using namespace std;

enum decreaseDir{kInit=0,kLeft,kUp,kLeftUp};

void LCS_Print(int** LCS_dirction,string pStr1,string pStr2,int row,int col);

int LCS(string pStr1,string pStr2)
{
	//if(!pStr1||!pStr2)return 0;

	int length1=pStr1.length();
	int length2=pStr2.length();

	if(!length1||!length2)return 0;

	int i,j;
	int** LCS_length;
    LCS_length=(int**)(new int[length1]);

	for(i=0;i<length1;i++)
		LCS_length[i]=(int*)new int[length2];
	for(i=0;i<length1;++i)
		for(j=0;j<length2;++j)
			LCS_length[i][j]=0;              //初始化length matrix

	int** LCS_dirction;
	LCS_dirction=(int**)(new int[length1]);
	for(i=0;i<length1;++i)
		LCS_dirction[i]=(int*)new int[length2];
	for(i=0;i<length1;++i)
		for(j=0;j<length2;++j)
			LCS_dirction[i][j]=kInit;          //初始化dirction matrix

	for(i=0;i<length1;++i)
	{
		for(j=0;j<length2;++j)
		{
			if(i==0||j==0)
			{
				if(pStr1[i]==pStr2[j])
				{
					LCS_length[i][j]=1;
					LCS_dirction[i][j]=kLeftUp;
				}
				else LCS_length[i][j]=0;
			}
			else if(pStr1[i]==pStr2[j])
			{
				LCS_length[i][j]=LCS_length[i-1][j-1]+1;
				LCS_dirction[i][j]=kLeftUp;
			}
			else if(LCS_length[i-1][j]>LCS_length[i][j-1])
			{
				LCS_length[i][j]=LCS_length[i-1][j];
				LCS_dirction[i][j]=kUp;
			}
			else
			{
				LCS_length[i][j]=LCS_length[i][j-1];
				LCS_dirction[i][j]=kLeft;
			}
		}
	}

	LCS_Print(LCS_dirction,pStr1,pStr2,length1-1,length2-1);

	return LCS_length[length1-1][length2-1];

}

void LCS_Print(int** LCS_dirction,string pStr1,string pStr2,int row,int col)
{
	//if(pStr1==NULL||pStr2==NULL)return;

	int length1=pStr1.length();
	int length2=pStr2.length();

	if(length1==0||length2==0||!(row<length1&&col<length2))return;

	if(LCS_dirction[row][col]==kLeftUp)
	{
	    if(row>0&&col>0)
		    LCS_Print(LCS_dirction,pStr1,pStr2,row-1,col-1);
	    printf("%c",pStr1[row]);
	}
	else if(LCS_dirction[row][col]==kLeft)
	{
		if(col>0)
			LCS_Print(LCS_dirction,pStr1,pStr2,row,col-1);
	}
	else if(LCS_dirction[row][col]==kUp)
	{
		if(row>0)
			LCS_Print(LCS_dirction,pStr1,pStr2,row-1,col);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	string str1="BDCABA";
	//char str1[]={'B','D','C','A','B','A'};
	string str2="ABCBDAB";
	//char str2[]={'A','B','C','B','D','A','B'};

	cout<<"存在的一個最大子串為："<<endl;
	int Length=LCS(str1,str2);
	
	cout<<endl<<"最大子串的長度為："<<Length<<endl;


	int k=0;
	cin>>k;
	return 0;
}
      

程式的運作截圖：