爱奇艺 平方串 动态规划

题目描述

如果一个字符串S是由两个字符串T连接而成,即S = T + T, 我们就称S叫做平方串,例如"","aabaab","xxxx"都是平方串.
牛牛现在有一个字符串s,请你帮助牛牛从s中移除尽量少的字符,让剩下的字符串是一个平方串。换句话说,就是找出s的最长子序列并且这个子序列构成一个平方串。

输入描述:

输入一个字符串s,字符串长度length(1 ≤ length ≤ 50),字符串只包括小写字符。

输出描述:

输出一个正整数,即满足要求的平方串的长度。

示例1

输入

frankfurt

输出

4

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e2+5;
int dp[maxn][maxn];
int main()
{
    string s;
    string s1;
    string s2;
    while(cin>>s)
    {
        int len = s.length();
        int ans=0;    
        for(int k=1;k<len;++k)
        {
            s1=s.substr(0,k);
            s2=s.substr(k,len-k);
            //cout<<s1<<"   "<<s2<<endl;
            int len1 = s1.length();
            int len2 = s2.length();
            memset(dp,0,sizeof(dp));
            int i,j;
            for(i=1;i<=len1;++i)
            {
                for(j=1;j<=len2;++j)
                {
                    if(s1[i-1]==s2[j-1])
                    {
                        dp[i][j]=dp[i-1][j-1]+1;
                    }else 
                    {
                        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                    }
                }                
            }
            //cout<<dp[i-1][j-1]<<endl;
            ans=ans>dp[i-1][j-1]?ans:dp[i-1][j-1];        
        }
        cout<<ans*2<<endl;
    }
    return 0;
}