Chương trình đếm số chuỗi con riêng biệt bằng s trong Python

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm số lượng các chuỗi con khác biệt không rỗng của s.

Vì vậy, nếu đầu vào là s =​​"abaa", thì đầu ra sẽ là 8 vì, các chuỗi con là ["a", "b", "ab", "ba", "aa", "aba", " trừu kêu "," abaa "].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• trie:=một bản đồ mới
• n:=kích thước của s
• đối với tôi trong phạm vi từ 0 đến n - 1, thực hiện
  • curr:=trie
  • đối với j trong phạm vi từ i đến n - 1, thực hiện
    • c:=s [j]
    • nếu c không có trong curr, thì
      • curr [c]:=một bản đồ mới
    • curr:=curr [c]
    • curr ["*"]:=True
• q:=tạo hàng đợi và chèn trie
• ans:=0
• trong khi q là không rỗng, hãy thực hiện
  • ans:=ans + 1
  • t:=mục bên trái của q và xóa mục này khỏi q
  • đối với mỗi c trong t, thực hiện
    • nếu c không giống như "*", thì
      • chèn t [c] vào cuối q
• return ans - 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

"abaa"

Đầu ra

8