Pythonで最長のパリンドローム部分文字列の長さを見つけるプログラム

文字列Sがあるとします。Sで最長の回文部分文字列の長さを見つける必要があります。文字列Sの長さは1000であると想定しています。したがって、文字列が「BABAC」の場合、最長の回文部分文字列は「BAB」です。長さは3です。

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

• 文字列の長さと同じ次数の正方行列を1つ定義し、Falseで埋めます

• 主対角要素をtrueに設定し、DP [i、i] =0からorder–1までのすべてのiに対してTrue

• start：=0

• 範囲2からS+1の長さのlの場合

  • 0からSの長さまでの範囲のiの場合– l + 1

    • 終了：=i + l

    • l =2の場合、

      • S [i] =S [end-1]の場合、

        • DP [i、end --1] =True、max_len：=l、およびstart：=i

    • それ以外の場合

      • S [i] =S[end-1]およびDP[i+ 1、end-2]の場合、

        • DP [i、end --1] =True、max_len：=l、およびstart：=i

• max_lenを返す

理解を深めるために、次の実装を見てみましょう-

例

class Solution(object):
   def solve(self, s):
      dp = [[False for i in range(len(s))] for i in range(len(s))]
         for i in range(len(s)):
            dp[i][i] = True
         max_length = 1
         start = 0
         for l in range(2,len(s)+1):
            for i in range(len(s)-l+1):

               end = i+l

               if l==2:
                  if s[i] == s[end-1]:
                     dp[i][end-1]=True
                     max_length = l
                     start = i
               else:
                  if s[i] == s[end-1] and dp[i+1][end-2]:
                     dp[i][end-1]=True
                  max_length = l
                  start = i
return max_length

ob = Solution()
print(ob.solve('BABAC'))

入力

"ABBABBC"

出力

5