lcs的一些写法

 

/************************************************************************/
/* lcs test                                                             */
/* 2011-2-9                                                             */
/************************************************************************/
#include <iostream>
#include <vector>
#include <string>
using namespace std;


string lcs_1_array2(string a, string b)
{
	if(a == "" || b == "")
		return "";
	int lenA = a.length();
	int lenB = b.length();
	int shortLen = min(lenA, lenB);
	int longLen = max(lenA, lenB);
	string& longStr = lenA > lenB ? a:b;
	string& shortStr = lenA > lenB ? b:a;

	int*arr = new int[shortLen];
	memset(arr, 0, sizeof(int)*shortLen);
	
	int maxPos = 0;
	int maxMatchLen = 0;
	int lastVal = 0;
	int oldVal = 0;
	
	for(int i = 0; i < longLen; i++) 
		for(int j = 0; j < shortLen; j++) 
		{
			oldVal = arr[j];
			if(longStr[i] == shortStr[j]) 
			{				
				if(j > 0)
					arr[j] = lastVal + 1;
				else 
					arr[j] = 1;
				if(arr[j] > maxMatchLen) 
				{
					maxMatchLen = arr[j];
					maxPos = j;
				}
			} 
			else 
			{
				arr[j] = 0;
			}
			lastVal = oldVal;
		}

	if(maxMatchLen == 0)
		return "";
	cout<<maxPos<<"  "<<maxMatchLen<<endl;
	return shortStr.substr(maxPos + 1 - maxMatchLen, maxMatchLen);
}

string lcs_2_array(string a, string b)
{
	if(a == "" || b == "")
		return "";
	int lenA = a.length();
	int lenB = b.length();
	int shortLen = min(lenA, lenB);
	int longLen = max(lenA, lenB);
	string& longStr = lenA > lenB ? a:b;
	string& shortStr = lenA > lenB ? b:a;

	int**arr = new int*[2];
	arr[0] = new int[shortLen];
	arr[1] = new int[shortLen];
	memset(arr[0], 0, sizeof(int)*shortLen);
	memset(arr[1], 0, sizeof(int)*shortLen);
	
	int maxPos = 0;
	int maxMatchLen = 0;

	for(int i = 0; i < longLen; i++) 
		for(int j = 0; j < shortLen; j++) 
		{
			if(longStr[i] == shortStr[j]) 
			{
				if(i > 0 && j > 0)
					arr[i%2][j] = arr[(i+1)%2][j-1] + 1;
				else 
					arr[i%2][j] = 1;
				if(arr[i%2][j] > maxMatchLen) 
				{
					maxMatchLen = arr[i%2][j];
					maxPos = j;
				}
			} 
			else 
			{
				arr[i%2][j] = 0;
			}
		}

	if(maxMatchLen == 0)
		return "";
	cout<<maxPos<<"  "<<maxMatchLen<<endl;
	return shortStr.substr(maxPos + 1 - maxMatchLen, maxMatchLen);
}


int main()
{

	string a, b;
	
	a = "312";
	b = "31233";

	cout<<"Test of 1 array"<<endl;
	cout<<lcs_1_array2(a, b)<<endl;

	cout<<"========================================="<<endl;

	cout<<"Test of 2 array"<<endl;
	cout<<lcs_2_array(a, b)<<endl;

	system("pause");
	return 0 ;
}