博客

    期末论文选的是最长公共子序列的其他解法，偶然发现Nakatsu算法对于最长公共子序列求解速度很快。呕心沥血写的代码=。=| 希望可以给以后想学习用Nakatsu算法的朋友们一个参考。 注：Nakatsu求的是最佳匹配度，子序列可能所含字符不正确，但却是基于Nakatsu算法的最佳匹配，求得的最长公共子序列的长度是一定对的。（没用使用STL容器，不是很熟练）

/******************************************
代码说明:
本程序定义了二维动态数组L[][]用来存储Nakatsu算法中计算相同字符对应位置的矩阵
最大值即不存在相等的字符
若L[][]对角线上任意一个位置为最大值，对角线上其余位置也是最大值，即本条对角线上不存在最大公共子序列
*******************************************/

//Nakatsu求解的是基于自身算法的最长公共子序列的最佳匹配度，在某些情况可能与最长公共子序列有所偏差，即长度一致，字符可能会偏差少许
#include <iostream>
#include <string>
#include <iomanip>
using namespace std;
void LCS_N(const string& a, const string& b)
{

	unsigned int i = 0;//循环控制变量也当做L[][i]数组列下标
	unsigned int j = 0;//循环控制变量
	unsigned int m = a.length();//短字符串长度
	unsigned int n = b.length();//长字符串长度
	unsigned p = m-1;//记录最长子序列长度
	unsigned int k=1;//L[k][]数组行下标

	unsigned int **L = new unsigned int *[m];//字符位置矩阵
	for (i = 0; i < m; i++)
		L[i] = new unsigned int[m];

	for (i = 0; i < m; i++)//将 下面的一条次对角线 初始化为最大值,对于unsigned int来说，-1，就是最大值
	{
		j = i + 1;
		if (j < m)
			L[j][i] = -1;
	}//for
	for (j = 0; j < m; j++)
		L[0][j] = 0;//第0行初始化为0


	for (unsigned int x=1;x<m;x++)
	{
		k=1;
		i=x;
		for(j=1;j<n&&i<m;j++)//匹配a[i]与b[j]
		{
			if(a[i]==b[j]||j>=L[k][i-1])
			{
				L[k][i]=j;
				k++;
				i++;
			}

		}
		//结束循环时，L[k][i]可能未赋值,L[k][i-1]可能为正常的值
		while(i<m)//如果未跳出循环，对这条对角线的剩余元素赋值，由于L[k][i-1]或为最大值，或为正常值，因此可以直接将L[k][i-1]赋值给L[k][i]
		{
			L[k][i]=L[k][i-1];
			i++;
			k++;
		}
		if(L[k-1][i-1]!=-1)//如果这条对角线最后一个元素不为最大值（即-1），说明找到完整对角线，跳出循环
			break;
		p--;

	}

	for(i=0;i<m;i++)//输出最长子序列位置（位置对应着长字符串中的字符），即完整的对角线上的数列，
	{
		for(j=0;j<m;j++)
			cout<<setw(11)<<L[i][j]<< "  ";
		cout<<endl;
	}//for
	
	cout<<"最长公共子序列长度为:"<<p<<endl;//输出最长公共子序列长度
	
	if(m-x!=0)
	{
		cout<<"最长公共子序列为:";
		for(i=1,j=x;i<=p;i++,j++)//输出最长公共子序列（最佳匹配）
			cout<<b[L[i][j]];
		cout<<endl;
	}
	
	for (i = 0; i < k; i++)//释放动态数组空间
		delete[] L[i];
	delete[] L;
}
int main()
{
	string a;
	string b;
	cout << "Please enter the first string:" << endl;
	cin >> a;
	cout << "Please enter the second string:" << endl;
	cin >> b;
	a = " " + a;
	b = " " + b;
	swap(a, b);
	LCS_N(a, b);
	return 0;
}