Python中最长的块回文分解

假设我们有一个文本。我们必须找到最大可能的k，使得存在a[1]，a[2]，...，a[k]，使得：每个a[i]是一个非空字符串；它们的串联a[1]+a[2]+...+a[k]等于给定的文本；对于1到k范围内的所有i，a[i]=a[{k+1-i}]。

因此，如果输入类似于“antaprezatepzapreanta”，则输出将为11，因为我们可以像“(a)(nt)(a)(pre)(za)(tpe)(za)(pre)（a）(nt)(a)”。

为了解决这个问题，我们将遵循以下步骤-

开始：=0，结束：=文本长度-1

用空字符串初始化temp1和temp2

当文本长度为奇数时，ans=1，否则为0

在开始<结束时，执行-

将temp1和temp2设置为空字符串

回答：=回答+2

temp1：=temp1+文字[开始]

temp2：=文本[结束]+temp2

如果temp1与temp2相同，则-

开始：=开始+1

结束：=结束-1

如果文本长度为偶数并且（temp1或temp2不为空）

ans：=ans+1

返回ans

让我们看下面的实现以更好地理解-

示例

class Solution(object): def longestDecomposition(self, text): start = 0 end = len(text)-1 temp1 = "" temp2 = "" ans = 1 if len(text) & 1 else 0 while start<end: temp1+=text[start] temp2 = text[end]+temp2 if temp1 == temp2: temp1 = temp2 = "" ans+=2 start+=1 end-=1 if len(text)%2 == 0 and(temp1 or temp2): ans += 1 return ans ob = Solution() print(ob.longestDecomposition("antaprezatepzapreanta"))

输入项

"antaprezatepzapreanta"

输出结果

11