首页 > 试题广场 >

平方串

[编程题]平方串

热度指数：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

输出

算法知识视频讲解

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)