โปรแกรมนับจำนวนสตริงย่อยที่แตกต่างกันใน s ใน Python

สมมติว่าเรามีสตริง s เราต้องหาจำนวนสตริงย่อยที่ไม่ว่างที่ชัดเจนของ s

ดังนั้น หากอินพุตเป็น s ="abaa" ผลลัพธ์จะเป็น 8 เพราะสตริงย่อยคือ ["a", "b", "ab", "ba", "aa", "aba", " baa", "abaa"].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ลอง :=แผนที่ใหม่
• n :=ขนาดของ s
• สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
  • curr :=พยายาม
  • สำหรับ j ในช่วง i ถึง n - 1 ทำ
    • c :=s[j]
    • ถ้า c ไม่อยู่ในสกุลเงิน แล้ว
      • curr[c] :=แผนที่ใหม่
    • curr :=curr[c]
    • curr["*"] :=จริง
• q :=สร้างคิวและแทรก trie
• ตอบ :=0
• ในขณะที่ q ไม่ว่าง ให้ทำ
  • อัน :=ans + 1
  • t :=เหลือรายการของ q และลบรายการนี้ออกจาก q
  • สำหรับแต่ละ c ใน t ทำ
    • ถ้า c ไม่เหมือนกับ "*" แล้ว
      • ใส่ t[c] ต่อท้าย q
• ส่งคืน ans - 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"

ผลลัพธ์

8