首页 > 试题广场 >

平方串

[编程题]平方串

热度指数：4056 时间限制：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

输出

算法知识视频讲解

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)

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)