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}]。

したがって、入力が「antaprezatepzapreanta」の場合、出力は11になります。これは、「（a）（nt）（a）（pre）（za）（tpe）（za）（pre）（」のように分割できるためです。 a）（nt）（a）"。

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

• start：=0、end：=テキストの長さ-1

• 空の文字列でtemp1とtemp2を初期化します

• テキストの長さが奇数の場合はans=1、それ以外の場合は0

• 開始<終了、実行-

  • temp1：=temp1 + text [start]

  • temp2：=text [end] + temp2

  • temp1がtemp2と同じ場合、-

    • temp1とtemp2を空の文字列として設定します

    • ans：=ans + 2

  • start：=start + 1

  • end：=end-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