首页 > 试题广场 >

平方串

[编程题]平方串

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

输出

算法知识视频讲解

TURBOTX

发表于 2023-03-16 12:27:30

import sys # 转换为求两字符串公共子串的最大长度 def maxCommon(s1, s2): dp = [[0 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)] for i in range(1,len 展开全文

牛客题解官

发表于 2020-06-05 17:46:18

题解题目难度：中等知识点：LCS（最长公共子序列问题），动态规划分析：本题实际是要找出s的最长子序列，看到这个问题就应该想到利用动态规划去解决。一般是找s1、s2两个字符串中的最长子序列，那么该题中就可以遍历s,以每个字符位置作为分割点，将s分割成s1和s2两个字符串，利用动态规划去求解s1 展开全文