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

  • i := 1, j := 文字長度 - 1

  • ic := 0, jc := 文字長度

  • 當 i <= j 時，執行以下操作：

    • 如果文字從索引ic到i-1的子串與文字從索引j到jc-1的子串相同，則

      • 計數器 := 計數器 + 2

      • ic := i

      • jc := j

    • i := i + 1

    • j := j - 1

  • 如果ic不等於jc，則

    • 計數器 := 計數器 + 1

  • 返回計數器

示例

讓我們看下面的實現來更好地理解。

def solve(text):
   counter = 0
   i, j = 1, len(text) - 1
   ic, jc = 0, len(text)

   while i <= j:
      if text[ic:i] == text[j:jc]:
         counter += 2
         ic = i
         jc = j
      i += 1
      j -= 1

   if ic != jc:
      counter += 1

   return counter

text = "antaprezatepzapreanta"
print(solve(text))

輸入

[3,4,5,2,1,7,3,4,7], 3

輸出

11

更新於：2021年10月8日

93 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告