【2018校招真题】平方串（python）

题目描述

如果一个字符串S是由两个字符串T连接而成,即S = T + T, 我们就称S叫做平方串,例如"","aabaab","xxxx"都是平方串.

牛牛现在有一个字符串s,请你帮助牛牛从s中移除尽量少的字符,让剩下的字符串是一个平方串。换句话说,就是找出s的最长子序列并且这个子序列构成一个平方串。
输入描述:

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

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

frankfurt
输出

4

解题思路

在不同位置将字符串切割成两个子串，然后采用动态规划的方式求解两个子串的公共子串大小。

完整代码

s = input()

def maxLen(a, b):
    len1 = len(a)
    len2 = len(b)
    dp = [[0 for j in range(len2 + 1)] for i in range(len1 + 1)]
    for i in range(1, len1 + 1):
        for j in range(1, len2 + 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[len1][len2] * 2

res = 0
for i in range(len(s) - 1):
    res = max(res, maxLen(s[0: i + 1], s[i+ 1: ]))
print(res)