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

<시간/>

소문자 문자열 s가 있다고 가정하고 s에서 최소 두 번 발생하는 가장 긴 부분 문자열의 길이를 찾아야 합니다. 그런 문자열을 찾을 수 없으면 0을 반환합니다.

따라서 입력이 s ="abdgoalputabdtypeabd"와 같으면 두 번 이상 발생하는 가장 긴 부분 문자열이 "abd"이기 때문에 출력은 3이 됩니다.

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

lcs() 함수를 정의합니다. s1, s2가 소요됩니다.
n :=s1 크기와 s2 크기 중 최소값
0 ~ n - 1 범위의 i에 대해
- s1[i]가 s2[i]와 같지 않으면
  - s1의 하위 문자열 반환[인덱스 0에서 i-1까지]
s1의 하위 문자열 반환[인덱스 0에서 n - 1까지]
메인 방법에서 다음을 수행하십시오. -
접미사 :=새 목록
n :=s의 크기
max_len :=0
0 ~ n - 1 범위의 i에 대해
- 접미사의 끝에 (s[인덱스 i에서 n - 1까지]의 부분 문자열) 삽입
목록 접미사 정렬
접미사의 부분 문자열에서 a 및 접미사의 부분 문자열에서 각 항목에 대해[인덱스 1에서 끝까지], do
- rtr :=lcs(a, b)
- rtr의 크기가 max_len이면
  - max_len :=rtr의 크기
max_len을 반환

예시

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

def lcs(s1, s2):
   n = min(len(s1), len(s2))

   for i in range(n):
      if s1[i] != s2[i]:
         return s1[:i]
   return s1[:n]

def solve(s):
   suffixes = []
   n = len(s)
   max_len = 0

   for i in range(n):
      suffixes.append(s[i:n])

   suffixes.sort()

   for a, b in zip(suffixes, suffixes[1:]):
      rtr = lcs(a, b)

      if len(rtr) > max_len:
         max_len = len(rtr)

   return max_len

s = "abdgoalputabdtypeabd"
print(solve(s))

입력

"abdgoalputabdtypeabd"