Pythonで最長のチャンク回文分解の長さを見つけるプログラム

テキストがあるとします。次のようなa[1]、a [2]、...、a[k]が存在するような最大のkを見つける必要があります。各a[i]は空白ではない文字列です。そして、それらの連結a [1] + a [2] + ... + a [k]は、指定されたテキストと同じです。 1からkの範囲のすべてのiについて、a [i] =a [{k+1--i}]。

したがって、入力がtext ="antaprezatepzapreanta"の場合、 "a | nt | a | pre | za | tpe | za | pre | a | nt | a"のように分割できるため、出力は11になります。

これを解決するには、次の手順に従います-

• カウンター：=0

• i：=1、j：=テキストのサイズ-1

• ic：=0、jc：=テキストのサイズ

• i <=j、do

  • テキストのサブストリング[インデックス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