โปรแกรมค้นหาจำนวนสตริงย่อยที่แตกต่างกันในสตริงที่กำหนดใน python

สมมติว่าเราได้รับสตริงย่อยที่แสดงด้วย 's' เราต้องหาสตริงย่อยที่ไม่ซ้ำกันและส่งคืนจำนวนสตริงย่อยเหล่านี้เป็นเอาต์พุต

ดังนั้น หากอินพุตเป็น s ='prrstvt' เอาต์พุตจะเป็น 26

สตริงย่อยที่แตกต่างกันจะเป็น −

'pr', 'rrs', 'st', 'rr', 'tv', 'rstv', 'stvt', 'prrstv', 'prrstvt', 'rrstvt', 's', 'prrst', 'stv ', 'rrstv', 'rst', 'v', 'tvt', 'rstvt', 'r', 'rs', 'vt', 't', 'prr', 'p', 'rrst', และ 'prs'

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

• เยี่ยมชมแล้ว :=แผนที่ใหม่
• สำหรับแต่ละดัชนี ind และค่าให้ใน s, do
  • temp :=ชุดใหม่
  • ถ้ามี ind-1 ในการเยี่ยมชม แล้ว
    • สำหรับแต่ละ has_let ในการเยี่ยมชม[ind-1] ทำ
      • เพิ่ม(has_let + ให้) ในรายการชั่วคราว
  • เพิ่ม(ให้) ในรายการชั่วคราว
  • เยี่ยมชม[ind] :=temp
• res :=ชุดใหม่
• สำหรับแต่ละชุดที่เข้าชม ทำ
  • add(visited[sets]) ไปยัง res
• ขนาดผลตอบแทนของความละเอียด

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(s):
   visited = dict()
   for ind, let in enumerate(s):
      temp = set()
      if ind-1 in visited:
         for has_let in visited[ind-1]:
            temp.add(has_let+let)
      temp.add(let)
      visited[ind] = temp
   res = set()
   for sets in visited:
      res.update(visited[sets])
   return len(res)

print(solve('prrstvt'))

อินพุต

'prrstvt'

ผลลัพธ์

26