两个字符串的最长公共子串

DP的方式求解：

#include <iostream>

using namespace std;

#define M 9
#define N 11
//如果动态传进m和n的话，数组lcs赋值只能通过指针，这样太麻烦
int lcs[M][N];

/**
* 最长公共子串(LCS)
* 状态转移方程：
* f(i,j) = 
	0				a[i] != b[j]
	f(i-1,j-1)+1	a[i] == b[j]
	其中f(i,j)表示串A以a[i]结尾与串B以b[j]结尾的最长公共子串
* 优化： 这里时间和空间都是O(M*N)。
*	注意到我们自底向上求解lcs[m][n]的时候，其实是
*	逐行求解的。每行只依赖于上一行的值，所以我们其实可以利用
*	“滚动数组”来优化这个DP解法的空间到O(N)。
*/
char *lcs1(char *a, char *b){
	int a_len = M,b_len = N;
	char *p;
	int i,j;
	int max = 0, end_y;

	//初始化二位数组的第0列
	p = a;
	for(i=0;i<a_len;i++){
		if(a[i] == b[0]) lcs[i][0] = 1;
		else lcs[i][0] = 0;
	}

	//初始化二维数组的第0行
	p = b;
	for(j=0;j<b_len;j++){
		if(b[j] == a[0]) lcs[0][j] = 1;
		else lcs[0][j] = 0;
	}

	/**
	* 核心部分：一行一行地自底向上求解
	*/
	for(i=1;i<a_len;i++)
		for(j=1;j<b_len;j++){
			//相同，则公共长度lcs[i][j]=lcs[i-1][j-1]+1
			if(*(a+i) == *(b+j)){
				lcs[i][j] = lcs[i-1][j-1] + 1;
				
				//记录最大长度的横坐标
				if(lcs[i][j] > max){
					max = lcs[i][j];
					end_y = i;
				}
			}
			//不同，公共长度为0
			else{
				lcs[i][j] = 0;
			}
		}

	//输出lcs矩阵
	for(i=0;i<a_len;i++){
		for(j=0;j<b_len;j++){
			cout<<lcs[i][j];
		}
		cout<<endl;
	}

	//将公共子串(从a串中取)放入新空间并返回
	p = (char *)malloc(sizeof(char)*(max+1));
	j = 0;
	for(i = end_y-max+1;i<=end_y;i++){
		*(p+j) = a[i];
		j++;
	}
	*(p+j) = '\0';

	return p;
}

int main(){
	char *a = "ackonpbee";
	char *b = "dcaconpbexx";
	cout<<"lcs:"<<lcs1(a,b)<<endl;;

	return 0;
}