hanyeah

问题描述：求两字符串的连续最大公共子字符串

属于动态规划问题，使用LCS算法。

参考：http://blog.csdn.net/yebanxin/article/details/52190683

如果我们用f(i,j)表示从字符串s1的第i个位值和s2的第j个位值开始匹配，可匹配的最大字符串长度。那么有这个关系f(i,j)=f(i+1,j+1)+1。

LCS算法的思路和优化都是根据这个公式来的。

自己用js写了一个。算法复杂度O(mn)。

zuidapipei("hello","hanellb");

function zuidapipei(a,b){
	var n1 = a.length;
	var n2 = b.length;
	var arr=[];
	for(var i=0;i<n1;i++){
		arr[i]=[];
		for(var j=0;j<n2;j++){
			if(a.charAt(i)===b.charAt(j)){
				arr[i][j]=1;
			}
			else{
				arr[i][j]=0;
			}
		}
	}
	console.log(clone(arr,n1,n2));
	for(var i=n1-2;i>=0;i--){
		for(var j=n2-2;j>=0;j--){
			if(arr[i+1][j+1]&&arr[i][j]){
				console.log(i,j,arr[i+1][j+1],arr[i][j]);
				arr[i][j]+=arr[i+1][j+1];
			}
		}
	}
	console.log(arr);

	var max = 0;
	var id1 = 0;
	var id2 = 0;
	for(var i=0;i<n1;i++){
		for(var j=0;j<n2;j++){
			if(arr[i][j]>max){
				max=arr[i][j];
				id1=i;
				id2=j;
			}
		}
	}

	console.log("最大匹配长度是：",max);
	console.log("匹配的字符串是:",a.substr(id1,max));

}

function clone(arr,n1,n2){
	var result = [];
	for(var i=0;i<n1;i++){
		result[i]=[];
		for(var j=0;j<n2;j++){
			result[i][j]=arr[i][j];
		}
	}
	return result;
}

还可以用LCS算法计算两个字符串的相似度。

https://www.cnblogs.com/three-zone/archive/2013/06/06/LevenshteinDistance.html