Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

주어진 문자열의 모든 회문 하위 문자열 찾기 - Python에서 2로 설정

<시간/>

문자열이 있다고 가정합니다. 그 문자열에서 회문 하위 문자열을 모두 찾아야 합니다. 여기서 aa와 aa는 하나가 아닌 두 개의 하위 문자열로 간주됩니다.

따라서 입력이 재분배기와 같으면 출력은 ['r', 'e', ​​'d', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider'가 됩니다. , 'i', 'd', 'e', ​​'r']

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

  • v :=새 목록
  • 위치 :=0.0
  • pos
  • rad :=pos - (정수로서의 위치)
  • (pos + rad) =0이고 (s[(pos - rad)의 정수]는 s[(pos + rad)의 정수]와 동일), do
    • v 끝에 s[(pos - rad)의 정수에서 정수(pos + rad + 1)까지]를 삽입합니다.
    • rad :=rad + 1
  • 위치 :=위치 + 0.5
  • 반환 v
  • 예제 코드

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

    def get_all_pal_sub(s):
       v = []
       pos = 0.0
       while pos < len(s):
          rad = pos - int(pos)
          while ((pos + rad) < len(s) and (pos - rad) >= 0 and (s[int(pos - rad)] == s[int(pos + rad)])):
             v.append(s[int(pos - rad): int(pos + rad + 1)])
             rad += 1
          pos += 0.5
       return v
    v = get_all_pal_sub("redivider")
    print(len(v))
    print(v)

    입력

    "redivider"

    출력

    13 ['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider', 'i', 'd', 'e', 'r']