lcs.m

来自「patten regnization source从1-14章能运行」· M 代码 · 共 67 行

function [lcscount, lcs_path, lcs_str, lcstable] = lcs(a, b)
%  LCS Longest (maximum) common subsequence
%	侩过:
%	[count, lcs_path, lcs_str, lcstable] = lcsm(a, b)
%	a: 涝仿 巩磊凯 1
%	b: 涝仿 巩磊凯 2
%	count: LCS狼 俺荐
%	lcs_path: lcs 抛捞喉惑俊辑狼 悼利拌裙过狼 烹茄 弥利 菩胶
%	lcs_str: LCS 巩磊凯
%	lcstable: 悼利拌裙过捞 利侩等LCS 抛捞喉

if nargin == 0, return; end

a = a(:).';
b = b(:).';
m = length(a);
n = length(b);
lcstable = zeros(m+1, n+1);
prevx = zeros(m+1, n+1);
prevy = zeros(m+1, n+1);
% 悼利拌裙过阑 荤侩窍咯 LCS 茫扁
for i=1:m,
	for j = 1:n,
		if a(i)==b(j),
			lcstable(i+1,j+1) = lcstable(i,j)+1;
			prevx(i+1,j+1) = i;
			prevy(i+1,j+1) = j;
		elseif lcstable(i,j+1) > lcstable(i+1,j),
			lcstable(i+1,j+1) = lcstable(i,j+1);
			prevx(i+1,j+1) = i;
			prevy(i+1,j+1) = j+1;
		else
			lcstable(i+1,j+1) = lcstable(i+1,j);
			prevx(i+1,j+1) = i+1;
			prevy(i+1,j+1) = j;
		end 
	end
end

% 檬扁 炼扒 力芭
lcstable = lcstable(2:end, 2:end);
prevx = prevx(2:end, 2:end)-1;
prevy = prevy(2:end, 2:end)-1;

% LCS 巩磊凯狼 辨捞 府畔
lcscount = lcstable(m, n);

% 悼利 拌裙过狼 弥利 菩胶 府畔
if nargout > 1,
	now = [m, n];
	prev = [prevx(now(1), now(2)), prevy(now(1), now(2))];
	lcs_path = now;
	while all(prev>0),
		now = prev;
		prev = [prevx(now(1), now(2)), prevy(now(1), now(2))];
		lcs_path = [lcs_path; now];
	end 
	lcs_path = flipud(lcs_path);
end

% LCS 巩磊凯 府畔
if nargout > 2,	
	temp = lcstable((lcs_path(:,2)-1)*m+lcs_path(:,1));  % 菩胶甫 蝶扼 LCS 墨款飘
	temp = [0; temp];
	index = find(diff(temp));
	lcs_str = a(lcs_path(index,1));
end