Python中最长的块回文分解

Z时代
2024-01-10
分类：综合

假设我们有一个文本。我们必须找到最大可能的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"))