Python에서 가장 긴 회문 부분 문자열의 길이를 찾는 프로그램

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

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

• 문자열의 길이와 같은 차수의 정사각 행렬을 하나 정의하고 False로 채웁니다.

• 주요 대각선 요소를 true로 설정하여 0에서 차수 – 1까지의 모든 i에 대해 DP[i, i] =True

• 시작 :=0

• 범위 2에서 S + 1까지의 길이에 대한 l

  • 범위 0에서 S – l + 1까지의 i에 대해

    • 끝 :=i + l

    • 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 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