链接1：http://blog.csdn.net/x_xiaoge/article/details/7376220
链接2：http://blog.csdn.net/x_xiaoge/article/details/7376217
链接3：http://www.cnblogs.com/huangxincheng/archive/2012/11/11/2764625.html
LCS
1、动态规划法：见链接1、3
int LCS( string leftString, string rightString )
{ int lenLeft = leftString.length();
int lenRight = rightString.length();
int **martix;
martix = new int *[lenLeft+1]; for (int i=0; i<=lenLeft; i++)
{
martix[i] = new int [lenRight+1];
} for (int i = 0; i <= lenLeft; i++)
martix[i][0] = 0; for (int j = 0; j <= lenRight; j++)
martix[0][j] = 0; for (int i = 1; i <= lenLeft; i++)
{
for (int j = 1; j <= lenRight; j++)
{
if (leftString[i-1] == rightString[j-1])
{
martix[i][j] = martix[i-1][j-1] + 1;
}
else
{
if (martix[i-1][j] >= martix[i][j-1])
martix[i][j] = martix[i-1][j];
else
martix[i][j] = martix[i][j-1];
}
}
} return martix[lenLeft][lenRight];
}
LCCS：
1、递归算法如下：
string GetLongestString(string strTmp1, string strTmp2,string strTmp3)
{
int len1 = strTmp1.length();
int len2 = strTmp2.length();
int len3 = strTmp3.length();
if (len1 > len2)
{
if (len1 > len3)
{
return strTmp1;
}
}
else if (len2 > len3)
{
return strTmp2;
}
return strTmp3;
} void LCCS(const std::string& str1, const std::string& str2,std::string& lccs)
{
if(str1.length() == || str2.length() == )
return; if(str1[] == str2[])
{
lccs += str1[];
LCCS(str1.substr(), str2.substr(), lccs);
}
else
{
std::string strTmp1,strTmp2,strTmp3; LCCS(str1.substr(), str2, strTmp1);
LCCS(str1, str2.substr(), strTmp2);
LCCS(str1.substr(), str2.substr(), strTmp3);
std::string strLongest = GetLongestString(strTmp1, strTmp2, strTmp3);
if(lccs.length() < strLongest.length())
lccs = strLongest;
}
}