파이썬에서 문자열과 그 부분 문자열의 전체 유사성을 찾는 프로그램

<시간/>

문자열 s가 있다고 가정합니다. 우리는 각각의 접미사와 함께 string s의 유사성의 합을 찾아야 합니다. 여기서 두 문자열의 유사성은 두 문자열에 공통적으로 가장 긴 접두사의 길이입니다.

따라서 입력이 s ="pqpqpp"와 같으면 문자열의 접미사가 "pqpqpp", "qpqpp", "pqpp", "qpp", "pp" 및 "p"이기 때문에 출력은 11이 됩니다. 문자열 "pqpqpp"와 이 부분 문자열의 유사성은 6,0,3,0,1 및 1입니다. 따라서 합계는 6 + 0 + 3 + 0 + 1 + 1 =11입니다.

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

길이 :=s의 크기
총계:=길이
z :=처음에 0을 포함하는 목록
l :=0, r :=0
범위 1에서 길이 - 1까지의 k에 대해
- k> r이면
  - 일치:=0
  - 인덱스 :=k
- 인덱스 <길이, do
  - s[index]가 s[match]와 같으면
    - 일치 :=일치 + 1
    - 인덱스 :=인덱스 + 1
  - 그렇지 않으면
    - 루프에서 나오다
- z 끝에 일치 항목 삽입
- 일치하는 경우> 0이면
  - 총계 :=총계 + 일치
  - l :=k
  - r :=인덱스-1
- 그렇지 않으면
  - z[k-l] <(r-k)+1이면
    - z 끝에 z[k-l] 삽입
    - 총계 :=총계 + z[k-l]
  - 그렇지 않으면
    - 일치 :=r-k
    - 인덱스 :=r
    - 인덱스 <길이, do
      - s[index]가 s[match]와 같으면
        
        일치 :=일치 + 1
        
        인덱스 :=인덱스 + 1
      - 그렇지 않으면
        
        루프에서 나오다
    - z 끝에 일치 항목 삽입
    - 총계 :=총계 + 일치
    - l :=k
    - r :=인덱스-1
총 수익

예시

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

def solve(s):
   length = len(s)
   total = length

   z = [0]
   l = 0
   r = 0

   for k in range(1,length):
      if k > r:
         match=0
         index = k
         while index < length:
            if s[index] == s[match]:
               match +=1
               index +=1
            else:
               break
         z.append(match)
         if match > 0:
            total+=match
            l = k
            r = index-1
      else:
         if z[k-l] < (r-k)+1:
            z.append(z[k-l])
            total+=z[k-l]
         else:
            match = r-k
            index = r
            while index < length:
               if s[index] == s[match]:
                  match +=1
                  index +=1
               else:
                  break
            z.append(match)
            total+=match
            l = k
            r = index-1
   return total

s = "pqpqpp"
print(solve(s))

입력

"pqpqpp"