Longest Common Subsequence

The longest common subsequence (LCS) is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

• C#
• VB.Net
• C
• C++

									/*****Please include following header files*****/
// string
/***********************************************/

/*****Please use following namespaces*****/
// std
/*****************************************/

#define MAX(a, b) (a > b ? a : b)

static int LongestCommonSubsequence(string s1, string s2, string &output)
{
	int i, j, k, t;
	int s1Len = s1.size();
	int s2Len = s2.size();
	int *z = (int*)calloc((s1Len + 1) * (s2Len + 1), sizeof(int));
	int **c = (int**)calloc((s1Len + 1), sizeof(int*));

	for (i = 0; i <= s1Len; ++i)
		c[i] = &z[i * (s2Len + 1)];

	for (i = 1; i <= s1Len; ++i)
	{
		for (j = 1; j <= s2Len; ++j)
		{
			if (s1[i - 1] == s2[j - 1])
				c[i][j] = c[i - 1][j - 1] + 1;
			else
				c[i][j] = MAX(c[i - 1][j], c[i][j - 1]);
		}
	}

	t = c[s1Len][s2Len];
	output = (char*)malloc(t);

	for (i = s1Len, j = s2Len, k = t - 1; k >= 0;)
	{
		if (s1[i - 1] == s2[j - 1])
			output[k] = s1[i - 1], i--, j--, k--;
		else if (c[i][j - 1] > c[i - 1][j])
			--j;
		else
			--i;
	}

	free(c);
	free(z);

	return t;
}
								

Example

									string s1 = "human";
string s2 = "chimpanzee";
string output = "";
int outputLen = LongestCommonSubsequence(s1, s2, output);
								

Output

									output: hman
outputLen: 4