파이썬에서 가장 긴 회문 부분 문자열

문자열 S가 있다고 가정합니다. S에서 가장 긴 회문 부분 문자열을 찾아야 합니다. 문자열 S의 길이가 1000이라고 가정합니다. 따라서 문자열이 "BABAC"이면 , 가장 긴 회문 부분 문자열은 "BAB"입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

• 문자열의 길이와 같은 차수의 정사각 행렬을 하나 정의하고 False로 채웁니다.
• 주대각선 요소를 true로 설정하여 0에서 차수 – 1까지 모든 i에 대해 DP[i, i] =True
• 시작:=0
• 2에서 S + 1까지의 범위에 있는 l
  • 0에서 S – l + 1까지의 범위에 있는 i의 경우
    • 끝 :=나는 + 나는
    • l =2이면
      • S[i] =S[end - 1]이면
        • DP[i, end - 1] =True, max_len :=l, 시작 :=i
    • 그렇지 않으면
      • S[i] =S[end - 1]이고 DP[i + 1, end - 2]이면
        • DP[i, end - 1] =True, max_len :=l, 시작 :=i
• 인덱스 시작부터 시작 + max_len까지의 부분 문자열 반환

예제(파이썬)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

class Solution(object):
   def longestPalindrome(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 s[start:start+max_length]
ob1 = Solution()
print(ob1.longestPalindrome("ABBABBC"))

입력

"ABBABBC"

출력

"BBABB"