爱奇艺-笔试刷题2018-07-13

题目描述：

/**
如果一个字符串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;
}