파이썬에서 문자열과 그 접미사의 유사성을 찾는 프로그램

문자열 'input_str'이 주어졌다고 가정합니다. input_str에서 모든 접미사를 결정하면; 예를 들어 문자열이 'abcd'인 경우 접미사는 'abc', 'bcd', 'cd', 'd'입니다. 이제 우리는 input_str에서 가장 긴 공통 접두사와 접미사의 길이로 input_str과 모든 접미사 간의 유사성을 확인합니다. input_str과 모든 접미사 간의 유사성의 합계를 반환해야 합니다.

따라서 입력이 input_str ='tpotp'와 같으면 출력은 7

'tpotp' 문자열의 모든 접미사는 'tpotp', 'potp', 'otp', 'tp' 및 'p'입니다.

input_str을 사용하여 모든 접미사의 유사성을 확인하면 다음을 얻습니다. -

'tpotp' similarity 5
'potp' similarity 0
'otp' similarity 0
'tp' similarity 2
'p' similarity 0

Sum of similarities = 5 + 0 + 0 + 2 + 0 = 7.

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

• return_list :=input_str의 크기를 포함하는 새 목록
• i :=1
• p :=0
• q :=0
• r :=0
• 내가
• q
• 반환 목록[i-q]>=q+p-i이면
  • r :=q + p - i
  • p :=0
  • q :=0
• 그렇지 않으면
  • return_list의 끝에 return_list[i-q] 삽입
  • 나는 :=나는 + 1
  • r :=0

def solve(input_str):
   return_list = [len(input_str)]
   i = 1
   p, q = 0,0
   r = 0
   while i < len(input_str):
      if q < i < (q+p):
         if return_list[i-q] >= q+p-i:
            r = q + p - i
            p, q = 0, 0
         else:
            return_list.append(return_list[i-q])
            i += 1
            r = 0
      else:
         while i + r < len(input_str) and input_str[r] == input_str[i+r]:
            r += 1
         return_list.append(r)
         p,q = r,i
         i += 1
         r = 0
      return sum(return_list)

print(solve('tpotp'))

'tpotp'

5