Chương trình tìm độ dài của chuỗi con palindromic dài nhất trong Python

Giả sử chúng ta có một chuỗi S. Chúng ta phải tìm độ dài của chuỗi con palindromic dài nhất trong S. Chúng ta giả sử rằng độ dài của chuỗi S là 1000. Vì vậy, nếu chuỗi là "BABAC", thì chuỗi con palindromic dài nhất là "BAB" và chiều dài là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một ma trận vuông có thứ tự giống như độ dài của chuỗi và điền nó bằng Sai

• Đặt các phần tử đường chéo chính là true, do đó DP [i, i] =True cho tất cả các i từ 0 đến order - 1

• bắt đầu:=0

• cho l trong phạm vi 2 đến độ dài của S + 1

  • cho tôi trong phạm vi từ 0 đến độ dài của S - l + 1

    • end:=i + l

    • nếu l =2 thì

      • nếu S [i] =S [end - 1] thì

        • DP [i, end - 1] =True, max_len:=l và start:=i

    • nếu không thì

      • nếu S [i] =S [end - 1] và DP [i + 1, end - 2] thì

        • DP [i, end - 1] =True, max_len:=l và start:=i

• trả về max_len

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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'))

Đầu vào

"ABBABBC"

Đầu ra

5