Python에서 주어진 문자열의 모든 고유 회문 하위 문자열 찾기

소문자 ASCII 문자가 포함된 문자열이 있다고 가정하면 이 문자열의 고유한 연속 회문 하위 문자열을 모두 찾아야 합니다.

따라서 입력이 "bddaaa"와 같으면 출력은 [a, aa, aaa, b, d, dd]

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

• m :=새 지도
• n :=s의 크기
• matrix :=n개의 0으로 구성된 두 개의 행 만들기
• s :="@" 연결 s 연결 "#"
• 0에서 1 사이의 j에 대해 다음을 수행합니다.
  • 온도 :=0
  • 행렬[j, 0] :=0
  • i :=1
  • 내가 <=n일 때, 하는 동안
    • s[i - temp - 1]은 s[i + j + temp]와 같으나, do
      • temp :=온도 + 1
    • 행렬[j, i] :=온도
    • k :=1
    • while(행렬[j, i - k]는 temp - k와 같지 않음) 및 k
    • 행렬[j,i+k] :=행렬[j, i-k]의 최소값
    • k :=k + 1
  • temp :=최대 온도 - k, 0
  • i :=i + k

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def find_substr(s):
   m = dict()
   n = len(s)
   matrix = [[0 for x in range(n+1)] for x in range(2)]
   s = "@" + s + "#"
   for j in range(2):
      temp = 0
      matrix[j][0] = 0
      i = 1
      while i <= n:
         while s[i - temp - 1] == s[i + j + temp]:
            temp += 1
         matrix[j][i] = temp
         k = 1
         while (matrix[j][i - k] != temp - k) and (k < temp):
            matrix[j][i+k] = min(matrix[j][i-k], temp - k)
            k += 1
         temp = max(temp - k, 0)
         i += k
   s = s[1:len(s)-1]
   m[s[0]] = 1
   for i in range(1,n):
      for j in range(2):
         for temp in range(matrix[j][i],0,-1):
            m[s[i - temp - 1 : i - temp - 1 + 2 * temp + j]] = 1
      m[s[i]] = 1
   for i in m:
      print (i)
find_substr("bddaaa")

입력

bddaaa

출력

a
aa
b
aaa
d
dd