近期，我在网上看了一些动态规划求字符串最长公共子序列的代码。可是无一例外都是处理英文字符串，当处理汉字字符串时。常常会出现乱码或者不对的情况。

我对代码进行了改动。使用wchar_t类型存储字符串，可以正确的处理英文字符串和汉字字符串的最长公共子序列。

代码例如以下：

#include "stdafx.h"

#include <iostream>

#define N 1000

using namespace std;

//str1存储字符串1，str2存储字符串2

wchar_t str1[N],str2[N];

//lcs存储最长公共子序列

wchar_t lcs[N];

//c[i][j]存储str1[1...i]与str2[1...j]的最长公共子序列的长度

int c[N][N];

//flag[i][j]标记是那种子问题

//flag[i][j]==0为str1[i]==str2[j]

//flag[i][j]==1为c[i-1][j]>=s[i][j-1]

//flag[i][j]==-1为c[i-1][j]<s[i][j-1]

int flag[N][N];

//

int getLCSlength(const wchar_t *s1, const wchar_t *s2)

{

	int i;

	int len1 = wcslen(s1);

	int len2 = wcslen(s2);

	for(i=1;i<=len1;i++)

		c[i][0] = 0;

	for(i=0;i<=len2;i++)

		c[0][i] = 0;

	int j;

	for(i=1;i<=len1;i++)

		for(j=1;j<=len2;j++)

		{

			if(s1[i-1]==s2[j-1])

			{

				c[i][j] = c[i-1][j-1] +1;

				flag[i][j] = 0;

			}

			else if(c[i-1][j]>=c[i][j-1])

			{

				c[i][j] = c[i-1][j];

				flag[i][j] = 1;

			}

			else

			{

				c[i][j] = c[i][j-1];

				flag[i][j] = -1;

			}

		}

		return c[len1][len2];

}

wchar_t* getLCS(const wchar_t *s1, const wchar_t *s2,int len,wchar_t *lcs)

{

	int i = wcslen(s1);

	int j = wcslen(s2);

	while(i&&j)

	{

		if(flag[i][j]==0)

		{

			lcs[--len] = s1[i-1];

			i--;

			j--;

		}

		else if(flag[i][j]==1)

			i--;

		else

			j--;

	}

	return lcs;

}

int main(int argc, wchar_t* argv[])

{

	//本函数用来配置地域的信息，设置当前程序使用的本地化信息

	setlocale(LC_ALL,"chs");

	int cases;

	cout<<"请输入案例的个数："<<endl;

	cin>>cases;

	while(cases--)

	{

		int i;

		cout<<"请输入字符串1："<<endl;

		wcin>>str1;

		cout<<"请输入字符串2："<<endl;

		wcin>>str2;

		int lcsLen = getLCSlength(str1,str2);

		cout<<"最长公共子序列长度："<<lcsLen<<endl;

		wchar_t *p = getLCS(str1,str2,lcsLen,lcs);

		cout<<"最长公共子序列为："<<endl;

		for(i=0;i<lcsLen;i++)

			wcout<<lcs[i];

		wcout<<endl;

	}

	return 0;

}