โปรแกรมค้นหาจำนวนสตริงย่อยต่าง ๆ ของสตริงสำหรับการสืบค้นที่แตกต่างกันใน Python

สมมติว่าเรามีสตริง s ที่มีความยาวเป็น n นอกจากนี้เรายังมีรายการคำถาม Q โดยที่ Q[i] มีคู่ (l, r) สำหรับแต่ละข้อความค้นหา เราต้องนับจำนวนสตริงย่อยที่แตกต่างกันของ s ในช่วงที่รวมระหว่าง l และ r

ดังนั้น หากอินพุตเป็น s ="ppqpp" Q =[(1,1),(1,4),(1,1),(0,2)] ผลลัพธ์จะเป็น [1,8, 1,5] เพราะ

• สำหรับการสืบค้น (1, 1) สตริงย่อยเดียวคือ 'p' ดังนั้นเอาต์พุตคือ 1

• สำหรับการสืบค้น (1, 4) สตริงย่อยคือ 'p', 'q', 'pq', 'qp', 'pp', 'pqp', 'qpp' และ 'pqpp' ดังนั้นเอาต์พุตจึงเป็น 8

• อีกครั้งสำหรับข้อความค้นหา (1, 1) สตริงย่อยเดียวคือ 'p' ดังนั้นผลลัพธ์คือ 1

• สำหรับข้อความค้นหา (0, 2) สตริงย่อยคือ 'p', 'q', 'pp', 'pq', 'ppq' ดังนั้นผลลัพธ์คือ 8

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

• กำหนดฟังก์ชัน kasai() นี่จะใช้เวลา s, suff, n
• lcp :=อาร์เรย์ขนาด n และเติม 0
• inv :=อาร์เรย์ขนาด n และเติม 0
• สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
  • inv[suff [i]] :=i
• k :=0
• สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
  • ถ้า inv [i] เหมือนกับ n-1 แล้ว
    • k :=0
    • ติดตามตอนต่อไป
  • j :=suff[inv [i] + 1]
  • ในขณะที่ i + k
  • k :=k + 1
• lcp[inv [i]] :=k
• ถ้า k> 0 แล้ว
  • k :=k - 1

ตัวอย่าง

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

def kasai (s, suff, n):
   lcp = [0] * n
   inv = [0] * n
   for i in range (n):
      inv [suff [i]] = i
   k = 0
   for i in range (n):
      if inv [i] == n-1:
         k = 0
         continue
      j = suff [inv [i] + 1]
      while i + k <n and j + k <n and s [i + k] == s [j + k]:
         k += 1
      lcp [inv [i]] = k
      if k> 0:
         k -= 1
   return lcp

def solve(s, Q):
   res = []
   for i in range (len(Q)):
      left, right = Q[i]
      sub = s [left: right + 1]
      length = right-left + 1

      suffix = [[i, sub [i:]] for i in range (length)]

      suffix.sort (key = lambda x: x [1])
      suff, suffix = [list (t) for t in zip (* suffix)]

      lcp = kasai (sub, suff, length)
      count = len (suffix [0])
      for i in range (length-1):
         count += len (suffix [i + 1]) - lcp [i]

      res.append(count)
   return res

s = "pptpp"
Q = [(1,1),(1,4),(1,1),(0,2)]
print(solve(s, Q))

อินพุต

"pptpp", [(1,1),(1,4),(1,1),(0,2)]

ผลลัพธ์

[1, 8, 1, 5]