首页 > 试题广场 >

平方串

[编程题]平方串

热度指数：4063 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

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

输出描述:

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

示例1

输入

frankfurt

输出

算法知识视频讲解

fixit

def max1(s1,s2):
    lens=[[0]*(len(s2)+1) for _ in range(len(s1)+1)]
    for i in range(1,len(s1)+1):
        for j in range(1,len(s2)+1):
            if s1[i-1]==s2[j-1]:
                lens[i][j]=lens[i-1][j-1]+1 
            else:
                lens[i][j]=max(lens[i-1][j],lens[i][j-1])
    return lens[len(s1)][len(s2)]
s=raw_input()
max2=0
for i in range(1,len(s)):
    max2=max(max1(s[:i],s[i:]),max2)
print max2*2

发表于 2017-12-10 17:54:09 回复(2)

酸辣粉不要辣_

s = input()
c = []
for index in range(1, len(s)):
    a = s[:index]
    b = s[index:]
    arr = [[0 for i in range(len(b) + 1)] for j in range(len(a) + 1)]
    num = 0
    for i in range(len(a)):
        for j in range(len(b)):
            if a[i] == b[j]:
                arr[i+1][j+1] = arr[i][j] + 1
                num = max(num, arr[i+1][j+1])
            else:
                arr[i+1][j+1] = max(arr[i+1][j], arr[i][j+1])
                num = max(num, arr[i+1][j+1])
    c.append(num)
print(max(c)*2)

动态规划求解最长公共子序列，将给定的字符串遍历截断为两部分，然后求得的最长公共子序列的长度的两倍就是我们需要的输出

发表于 2019-06-16 17:23:24 回复(0)

wylu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();

        int res = 0;
        for (int i = 1; i < s.length(); i++) {
            res = Math.max(res, lcs(s.substring(0, i), s.substring(i)));
        }
        System.out.println(res * 2);
    }

    //求s1和s2的最长公共子序列的长度
    private static int lcs(String s1, String s2) {
        //dp[i + 1][j + 1]: 以s1[i]、s2[j]为结尾的最长公共子序列的长度
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }
}

发表于 2019-01-31 00:52:31 回复(1)

C/C++

霍七

本套3道题的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)，牛客网上的其他题目解答也在持续更新。
本道题考察最长公共子序列，在原序列任意点断开，分为左右两个序列，这两个序列的最长公共子序列就是以此点为中点的最长平方串，遍历所有断开的点及找到最长平方串。

#include 
#include 
#include 
#include 
using namespace std;
int main()
{
    string sequence; cin >> sequence;
    int len = sequence.length();
    int maxlen = 0;
    for (int k = 1; k < len; k++) {
        int **DP = new int*[k];
        for (int i = 0; i < k; i++) {
            DP[i] = new int[len - k];
            memset(DP[i], 0, sizeof(int)*(len - k));
        }
        DP[0][0] = sequence[0] == sequence[k] ? 1 : 0;
        for (int i = 1; i < k; i++) {
            DP[i][0] = sequence[i] == sequence[k] ? 1 : DP[i - 1][0];
        }
        for (int i = 1; i < len - k; i++) {
            DP[0][i] = sequence[0] == sequence[k + i] ? 1 : DP[0][i - 1];
        }
        for (int i = 1; i < k; i++) {
            for (int j = 1; j < len - k; j++) {
                DP[i][j] = sequence[i] == sequence[k + j] ? DP[i - 1][j - 1] + 1 : DP[i - 1][j - 1];
                DP[i][j] = max(DP[i][j], DP[i - 1][j]);
                DP[i][j] = max(DP[i][j], DP[i][j - 1]);
            }
        }
        maxlen = max(maxlen, DP[k - 1][len - k - 1]);
        for (int i = 0; i < k; i++) {
            delete[] DP[i];
        }
        delete[] DP;
    }
    cout << maxlen * 2 << endl;
    return 0;
}

编辑于 2017-12-21 10:43:57 回复(1)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int F(string a, string b){
    int n=a.length(), m=b.length();
    int dp[n+1][m+1];
    memset(dp, 0, sizeof(dp));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(a[i]!=b[j])
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
            else
                dp[i+1][j+1] = dp[i][j] + 1;
    return dp[n][m];
}

int main(){
    string s;
    cin>>s;
    int Max = 0;
    for(int i=1;i<s.length()-1;i++)
        Max = max(Max, 2*F(s.substr(0,i), s.substr(i)));
    printf("%d\n", Max);
    return 0;
}

发表于 2020-10-19 02:01:14 回复(0)

Python

笑一笑十年少

s = input().strip() def lcs(a, b):
    dp = [[0 for i in range(len(b) +1)] for i in range(len(a) + 1)] for i in range(1, len(a) + 1): for j in range(1, len(b) + 1): if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1  else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[len(a)][len(b)]
result = 0 for i in range(1, len(s) - 1):
    result = max(result, lcs(s[:i], s[i:])) print(result * 2)

编辑于 2019-05-28 16:11:54 回复(2)

乔碧萝殿下

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < str.length(); i++){
            max = Math.max(max, lcs(str.substring(0, i), str.substring(i)));
        }
        System.out.println(2 * max);
    }
    
    public static int lcs(String str1, String str2) {
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        for(int i = 0; i < str1.length(); i++) 
            for(int j = 0; j < str2.length(); j++) 
                dp[i + 1][j + 1] = str1.charAt(i) == str2.charAt(j) ? 
                        dp[i][j] + 1 : Math.max(dp[i + 1][j], dp[i][j + 1]);
        return dp[str1.length()][str2.length()];
    }
}

发表于 2019-03-20 21:11:24 回复(0)

Java

成程晨

import java.util.*;
public class Main{
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            String s = in.nextLine();
            int max = 0;
            for(int i = 1;i < s.length();i++){
                max = Math.max(max,helper(s.substring(0,i),s.substring(i)));
            }
            System.out.println(2 * max);
        }
    }
    public static int helper(String s1,String s2){
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for(int i = 0;i < s1.length();i++){
            for(int j = 0;j < s2.length();j++){
                dp[i + 1][j + 1] = s1.charAt(i) == s2.charAt(j) ? dp[i][j] + 1 : Math.max(dp[i][j + 1],dp[i + 1][j]); 
            }
        }
        return dp[s1.length()][s2.length()];
    }
}

发表于 2019-02-12 13:42:09 回复(1)

3VVV

思路：LCS,

#include<iostream>

#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<algorithm>
using namespace std;

int dp[55][55];
int LCS(string s1,string s2) {
memset(dp, 0, sizeof(dp));
for (int i = 1; i <s1.size(); i++) {
for (int j = 1; j <s2.size(); j++) {
if (s1[i] == s2[j])
dp[i][j] = dp[i - 1][j - 1] + 1;
else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[s1.size()-1][s2.size()-1];
}
int main()
{
string str, s1, s2;
cin >> str;
int len = str.length();
int ans = 0;
for (int i = 1; i < len; i++) {
s1 = " " + str.substr(0, i+1);
s2 = " " + str.substr(i+1);
int tmp = LCS(s1,s2)*2;
if (ans<tmp) {
ans = tmp;
}
}
cout << ans << endl;
return 0;
}

发表于 2018-09-15 00:18:18 回复(0)

小河沟大河沟

//平方串
#include<iostream>

using namespace std;

#include <string>

#define max(a,b)    (((a) > (b)) ? (a) : (b))


//测试用例:
//fjkjsakljflkjakljjfiwoqjfioq wfoiqwjfiojq
//
//对应输出应该为 :
//
//16
//
//你的输出为 :
//
//      18


int findMaxCom(string a_, string b_)
{
    int dp[51][51] = { 0 };
    int ret = 0;

    for (int i = 1; i <= a_.size();i++)
    {
        for (int j = 1; j <= b_.size();j++)
        {
            if (a_[i-1]==b_[j-1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }

            //ret = (ret > dp[i][j]) ? ret : dp[i][j];
        }
    }
    ret=dp[a_.size()][b_.size()];

    return ret;
}

int main()
{
    string str;
    char temp[50];
    cin >> str;
    int ret = 0;
    string a,b;
    for (int i = 0; i < str.size(); i++)
    {
        a = str.substr(0, i), b = str.substr(i, str.size()-i);

        int max_com_len = findMaxCom(a,b);

        ret = ret>max_com_len ? ret : max_com_len;
    }

    cout << ret * 2 << endl;
    return 0;
}

犯了一个细错误，浪费了几个小时找错误！当i,j =1开始用if (a_[i-1]==b_[j-1])

发表于 2017-12-19 19:40:55 回复(1)

程橙橙要码力全开

暴力方法，每个位置切一刀，字符串变成了两个部分，然后用动态规划求两个字符串的最长公共子序列，最后返回整体的最大值


	#include<iostream>



	#include<string>



	usingnamespacestd;



	 



	intMaxLength(string s,ints2)//从s2位置把字符串切开



	{



	    intc[50][50]={0};



	    if(s2 >= s.size())    return0;



	    intsize1 = s2, size2 = s.size() - s2; for(inti = 1; i <= size1; i++){



	        for(intj = 1; j <= size2; j++){



	            if(s[i - 1] == s[s2 + j - 1]){



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



	            }



	            else{



	                c[i][j] = max(c[i - 1][j], c[i][j - 1]);



	            }



	        }



	    }



	    returnc[size1][size2];



	}



	intmain()



	{



	    string str;



	    cin>>str;



	    intmax=0;



	    intsize=str.size();



	    for(inti=0;i<size;i++)



	    {



	        inttmp;



	        tmp=MaxLength(str,i);



	        if(tmp>max)



	            max=tmp;



	    }



	    cout<<2*max;



	    return0;



	}

编辑于 2017-11-28 13:08:33 回复(0)

元气の悟空

import java.util.*;
public class Main {
    public static void main(String[]args){
        Scanner in=new Scanner(System.in);
        String s=in.next();
        if(s.length()==1) System.out.println(0);
        else{
            int res=0,i,n=s.length();
            for(i=0;i+1<n;i++)
                res=Math.max(res,maxLen(s.substring(0,i+1),s.substring(i+1)));
            System.out.println(res);
        }
    }
    public static int maxLen(String a,String b){
        int len1=a.length(),len2=b.length(),i,j;
        int [][]dp=new int[len1+1][len2+1];
        for(i=1;i<=len1;i++)
            for(j=1;j<=len2;j++)
                dp[i][j]=(a.charAt(i-1)==b.charAt(j-1)
                ?dp[i-1][j-1]+1:Math.max(dp[i-1][j],dp[i][j-1]));
        return dp[len1][len2]*2;
    }
}

发表于 2017-11-28 20:00:53 回复(3)

名柳字思牧

def MaxS(s,l,n):
    #l为分割线
    dp = [[0]*(l+1) for _ in range(n-l+1)]
    M = 0
    for i in range(n-l):
        for j in range(l):
            if s[j]==s[l+i]:
                dp[i+1][j+1]=dp[i][j]+1
            else:
                dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
            M = max(M,dp[i+1][j+1])
    return M

s = input()
n = len(s)
R = 0
mid = int(n/2)
flag = 1
for i in range(1,n):
    if min(mid,n-mid)<=R:
        break
    M = MaxS(s,mid,n)
    R = max(M,R)
    mid += flag*i
    flag = -flag
print(2*R)

切一刀，然后动态规划，切刀时优先从中间切，方便剪枝，速度一流

发表于 2021-03-16 11:42:46 回复(0)

Java

何止hz

dp求最长公共子序列

import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-05-15 8:12
 * @Description: 平方串
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String l, r;
        int ans = 0;
        for (int i = 1; i < s.length(); i++){
            l = s.substring(0, i);
            r = s.substring(i);
            int dp[][] = new int[l.length()+1][r.length()+1];
            for (int m = 1; m <= l.length(); m++)
                for (int n = 1; n <= r.length(); n++){
                    if (l.charAt(m-1) == r.charAt(n - 1)){
                        dp[m][n] = dp[m-1][n-1] + 1;
                    }else {
                        dp[m][n] = Math.max(dp[m-1][n], dp[m][n-1]);
                    }
                }
            ans = Math.max(ans, dp[l.length()][r.length()]);
        }
        System.out.println(2 * ans);
    }
}

发表于 2020-05-15 08:37:59 回复(0)

阿耀哥

解题思路，暴力分解成两个子串，然后动态规划求两个子串的公共子序列。通过学习下面的算法思路

https://blog.csdn.net/someone_and_anyone/article/details/81044153

发表于 2020-02-07 11:41:56 回复(0)

魏无忌

每个位置都切一刀，把原字符串分成两部分，求解两部分的最长公共子串，最长的公共子串的长度的2倍即为所求

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int LCS(string s1, string s2){
    const int maxn = 60;
    int dp[maxn][maxn];
    for(int i=0; i < maxn; i++){
        dp[i][0] = 0;
        dp[0][i] = 0;
    }
    for(int i = 0; i < s1.size(); i++){
        for(int j = 0; j < s2.size(); j++){
            if(s1[i] == s2[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[s1.size()][s2.size()];
}
 
 
 
int main()
{
    string s;
    cin >> s;
    int result = 0;
    for(int i=0; i < s.size(); i++){
        string s1 = s.substr(0, i+1);
        string s2 = s.substr(i+1, s.size()-(i+1));
        int temp = LCS(s1, s2);
        result = max(temp, result);
//      cout << s1 << " " << s2 << " " << result << endl;
    }
    cout << result*2;
    return 0;
}

发表于 2019-09-18 16:48:42 回复(0)

源_Bob

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int LCS(string s1, string s2) {
	const int len1 = s1.length(), len2 = s2.length();
	vector<vector<int>> lcs(len1 + 1, vector<int>(len2 + 1, 0));
	for (int i = 0; i < len1; ++i)
		for (int j = 0; j < len2; ++j) {
			if (s1[i] == s2[j])
				lcs[i + 1][j + 1] = lcs[i][j] + 1;
			else
				lcs[i + 1][j + 1] = max(lcs[i][j + 1], lcs[i + 1][j]);
		}
	return lcs[len1][len2];
}

int main() {
	string s;
	cin >> s;
	int max_len = 0;
	for(size_t i = 1; i < s.length() - 1; ++i)
		max_len = max(max_len, 2 * LCS(s.substr(0, i), s.substr(i)));
	cout << max_len << endl;
}

发表于 2019-09-08 13:36:57 回复(0)

嘎嘎嘎~

//递归，果然超时了。分成两个子序列，两个序列求最长公共子序列的问题，动态规划
import java.util.*;// 递归
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            CAL(sc);
        }
    }
    public static void CAL(Scanner sc){
        String s=sc.next();
        int i=0;
        System.out.println(DIGUI(s,0));
    }
    public static int DIGUI(String s,int n){
        if (PanDu(s)) {  int jj=s.length();
            return s.length();
        }
        if(s.length()-1<n) {  return 0;
        }
        return Math.max(DIGUI(s.substring(0,n)+s.substring(n+1),n),DIGUI(s,n+1)) ;   }
    public static boolean PanDu(String s){
        if(s.length()%2==1) return false;
        else{
            String s1=s.substring(0,s.length()/2);
            String s2=s.substring(s.length()/2);
            if(s1.equals(s2)) return true;
            else return false;
        }
    }
}

//动态规划
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            CAL(sc);
        }
    }
    public static void CAL(Scanner sc){
        String s=sc.next();
        int n=s.length();
        int R=0;
        for(int i=0;i<n;i++) {
            int t=Hel(s.substring(0,i),s.substring(i));
            if (t>R) {
                R=t;
            }
        }
        System.out.println(R*2);
    }
    public static int Hel(String s1,String s2) {         //求s1和s2最长公共子序列
        int[][] dp=new int[s2.length()+1][s1.length()+1];
        for(int i=1;i<=s2.length();i++) {
            for(int j=1;j<=s1.length();j++) {
                if(s2.charAt(i-1)==s1.charAt(j-1)) {
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else {
                        dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[s2.length()][s1.length()];     }
}

编辑于 2019-06-10 19:17:43 回复(0)

xzzwzj

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int maxLengthString(string A,string B){
    int length=0;
    vector<int> input(B.size()+1);
    //int length_string=A.size()>B.size()?A.size():B.size();
    vector<vector<int> > record;
    for(int s1=0;s1<=A.size();s1++){
        record.push_back(input);
    }
    for(int k1=1;k1<=A.size();k1++){
        for(int k2=1;k2<=B.size();k2++){
//cout<<'A';
            if(A[k1-1]==B[k2-1]){
                record[k1][k2]=1+record[k1-1][k2-1];
            }

            else{
                record[k1][k2]=max(record[k1-1][k2],record[k1][k2-1]);
            }
        }
    }
    //cout<<B;cout<<A<<endl;
    return record[A.size()][B.size()];
}
int main(){
string input;
string tmp,A,B;
cin>>input;
tmp=input;
int length=input.size();
int kl=0;
for(int k=1;k<length;k++){
input=tmp;
A=input.substr(k);
input=tmp;
B=input.substr(0,k);
int kl1=maxLengthString(A,B);
    if(kl<kl1){kl=kl1;}
}
cout<<kl*2;
return 0;

}

发表于 2019-04-21 23:34:17 回复(1)

清上谨

s=input()

ans=0
n=len(s)
for i in range(1,n):
    dp=[[0]*55 for i in range(55)]
    for j in range(1,i+1):
        for k in range(i+1,n+1):
            if s[j-1]==s[k-1]:
                dp[j][k]=dp[j-1][k-1]+1
            else:
                dp[j][k]=max(dp[j-1][k],dp[j][k-1])
    ans=max(dp[i][n],ans)
print(ans*2)

发表于 2019-04-10 18:10:12 回复(0)