lcs_b.m

来自「一个关于数据聚类和模式识别的程序,在生物化学,化学中因该都可以用到.希望对大家有」· M 代码 · 共 67 行

function [lcscount, lcsstring, ind1, ind2, lcstable] = lcs(a, b)
%LCS Longest (maximum) common subsequence
%	Usage:
%	[count, string, index1, index2, lcstable] = lcs(a, b)
%	a: input string 1
%	b: input string 2
%	count: count of LCS
%	string: LCS string
%	index1: a(index1) is equal to LCS string
%	index2: b(index2) is equal to LCS string
%	lcstable: LCS table for applying dynamic programming
%
%	Type "lcs" for a self-demo.

% Roger Jang, 981226

if nargin == 0,
	a = 'abcdefghijk';
	b = 'cxxfxxhix';
	[count, string, ind1, ind2, table] = lcs(a, b);
	fprintf('Input string A is ''%s''\n', a);
	fprintf('Input string B is ''%s''\n', b);
	fprintf('Length of LCS is %i\n', count);
	fprintf('LCS is %s\n', string);
	fprintf('LCS index into string A is:\n');
	disp(ind1);
	fprintf('LCS index into string B is:\n');
	disp(ind2);
	fprintf('LCS table for dynamic programming is\n');
	disp(table);
end

a = a(:).';
b = b(:).';
m = length(a);
n = length(b);
lcstable = zeros(m+1, n+1);
lcstable(1,:) = 0;	%Initial condition
lcstable(:,1) = 0;	%Initial condition
% Find LCS using dynamic programming
for i=2:m+1,
	for j = 2:n+1,
		if a(i-1)==b(j-1),
			lcstable(i,j) = lcstable(i-1,j-1)+1;
		else
			lcstable(i,j) = max([lcstable(i-1,j) lcstable(i,j-1)]);
		end 
	end
end

% Get rid of initial conditions
lcstable(1,:) = [];
lcstable(:,1) = [];

% Return output arguments
lcscount = lcstable(m, n);
if nargout >= 2,
	ind1 = zeros(1, lcscount);
	ind2 = zeros(1, lcscount);
	for k = 1:lcscount,
		[i, j] = find(lcstable == k);
		ind1(k) = min(i);
		ind2(k) = min(j);
	end
	lcsstring = a(ind1);
end