Python에서 s의 고유한 하위 문자열 수를 계산하는 프로그램

<시간/>

문자열 s가 있다고 가정하고 s의 비어 있지 않은 고유한 하위 문자열의 수를 찾아야 합니다.

따라서 입력이 s ="abaa"와 같으면 하위 문자열이 ["a", "b", "ab", "ba", "aa", "aba", "이기 때문에 출력은 8이 됩니다. 바아", "아바아"].

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

trie :=새 지도
n :=s의 크기
0 ~ n - 1 범위의 i에 대해
- curr :=시도
- i ~ n - 1 범위의 j에 대해
  - c :=s[j]
  - c가 curr에 없으면
    - curr[c] :=새 지도
  - curr :=curr[c]
  - curr["*"] :=참
q :=대기열을 만들고 삽입 시도
ans :=0
q가 비어 있지 않은 동안 do
- ans :=ans + 1
- t :=q의 왼쪽 항목, q에서 이 항목 삭제
- t의 각 c에 대해 다음을 수행합니다.
  - c가 "*"와 같지 않으면
    - q 끝에 t[c] 삽입
반환 - 1

예시

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

from collections import deque
def solve(s):
   trie = {}
   n = len(s)
   for i in range(n):
      curr = trie
      for j in range(i, n):
         c = s[j]
         if c not in curr:
            curr[c] = {}
         curr = curr[c]
         curr["*"] = True

   q = deque([trie])
   ans = 0
   while q:
      ans += 1
      t = q.popleft()
      for c in t:
         if c != "*":
            q.append(t[c])
   return ans - 1

s = "abaa"
print(solve(s))

입력

"abaa"