题目描述：
/**
如果一个字符串S是由两个字符串T连接而成,即S = T + T,
我们就称S叫做平方串,
例如"","aabaab","xxxx"都是平方串.
牛牛现在有一个字符串s,
请你帮助牛牛从s中移除尽量少的字符,让剩下的字符串是一个平方串。
换句话说,就是找出s的最长子序列并且这个子序列构成一个平方串。
输入描述:
输入一个字符串s,字符串长度length(1 ≤ length ≤ 50),
字符串只包括小写字符。
输出描述:
输出一个正整数,即满足要求的平方串的长度。
输入例子1:
frankfurt
输出例子1:
4
*/
思路如下：
把原来字符串分割成长度为len1和len2的两个字符串
求这两个字符串最大的公共子序列
时间复杂度O(len1, len2)
总体复杂度 累加(i*(n-i)) (i从1到n-1)
总体时间复杂度O(n^3)其中n是字符串总长度在1-50范围内
可以接受
代码如下：
#include<stdio.h>
#include<iostream>
#define MAX_N 55
using namespace std;
int dp[MAX_N][MAX_N];
int LCS(string str1, string str2){
int len1=str1.size();
int len2=str2.size();
for(int i=0; i<len1; i++){
for(int j=0; j<len2; j++){
if(str1[i]==str2[j]){
dp[i+1][j+1]=dp[i][j]+1;
}
else{
dp[i+1][j+1]=max(dp[i][j+1], dp[i+1][j]);
}
}
}
return dp[len1][len2];
}
int main()
{
string line;
cin>>line;
int res=0;
for(int i=0; i<line.size()-1; i++){
string str1=line.substr(0, i+1);
string str2=line.substr(i+1, line.size()-i-1);
//cout<<str1<<" "<<str2<<" "<<LCS(str1, str2)<<endl;
res=max(res, LCS(str1, str2));
}
printf("%d", 2*res);
return 0;
}
