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

สมมติว่าเรามีสองสตริง s และชุดของแบบสอบถาม Q โดยที่ Q[i] มีคู่ (l, r) สำหรับแต่ละสตริงย่อยของ s จาก l ถึง r เราต้องหาจำนวนสตริงย่อย s จาก x ถึง y โดยที่พวกเขา มีความคล้ายคลึงกัน สองสตริง s และ t จะคล้ายกันหากปฏิบัติตามกฎเหล่านี้ -

• มีความยาวเท่ากัน

• สำหรับดัชนีแต่ละคู่ (i, j) หาก s[i] เหมือนกับ s[j] ดัชนีนั้นจะต้องเป็นไปตาม t[i] =t[j] และในทำนองเดียวกัน หาก s[i] ไม่เหมือนกับ s [j] จากนั้น t[i] และ t[j] จะต้องแตกต่างกัน

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

• สำหรับการค้นหาครั้งแรก สตริงย่อยที่คล้ายกันคือ "hj", "jh", "hb", "bc", "cb" และ "bk"
• สำหรับการค้นหาครั้งแรก สตริงย่อยที่คล้ายกันคือ "jhh"

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

• fp :=รายการใหม่
• กำหนดฟังก์ชัน calc_fingerprint() นี่จะใช้เวลา s
• dict :=พจนานุกรมใหม่ และเริ่มใส่คู่คีย์-ค่า (s[0], 0)
• fp :="0"
• j :=1
• สำหรับ i ในช่วง 1 ถึงขนาด s - 1 ทำ
  • ถ้า s[i] ไม่มีอยู่ใน dict แล้ว
    • dict[s[i]] :=j
    • j =j+1
  • fp :=fp + การแสดงสตริงของ dict[s[i]]
• ส่งคืนรูปแบบจำนวนเต็มของ fp
• จากวิธีหลัก ให้ทำดังต่อไปนี้ −
• ถ้าขนาด s> 10 แล้ว
  • สำหรับฉันในช่วง 0 ถึงขนาด s - 10 ทำ
    • x :=calc_fingerprint(s[จากดัชนี i ถึง i+9])
    • แทรก x ที่ส่วนท้ายของ fp
• ret :=รายการใหม่
• สำหรับฉันในช่วง 0 ถึงขนาด Q - 1 ทำ
  • (a, b) :=Q[i]
  • s1 :=สตริงย่อยของ s จากดัชนี a-1 ถึง b-1
  • k :=0
  • สำหรับ i ในช่วง 0 ถึงขนาด s - (b-a), do
    • ถ้า b-a> 9 และ fp[a-1] ไม่เหมือนกับ fp[i] แล้ว
      • ติดตามตอนต่อไป
    • dict :=แผนที่ใหม่ที่ว่างเปล่า
    • s2 :=สตริงย่อยของ s จากดัชนี i ถึง i+(b-a)
    • สำหรับฉันในช่วง 0 ถึง b-a ทำ
      • ถ้า s2[i] ไม่อยู่ใน dict แล้ว
        • ถ้า s1[i] อยู่ในค่าของ dict แล้ว
          • ออกมาจากลูป
        • dict[s2[i]] :=s1[i]
      • ถ้า dict[s2[i]] ไม่เหมือนกับ s1[i] แล้ว
        • ออกมาจากลูป
    • มิฉะนั้น
      • k :=k + 1
  • ใส่ k ต่อท้าย ret
• คืนสินค้า

ตัวอย่าง

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

fp = []

def calc_fingerprint(s):
   dict = {s[0]: 0}
   fp = "0"
   j = 1
   for i in range(1, len(s)):
      if s[i] not in dict:
         dict[s[i]], j = j, j+1
      fp += str(dict[s[i]])
   return int(fp)

def solve(s, Q):
   if len(s) > 10:
      for i in range(0, len(s)-10):
         fp.append(calc_fingerprint(s[i: i+10]))

   ret = []
   for i in range(len(Q)):
      a, b = Q[i]
      s1 = s[a-1:b]
      k = 0
      for i in range(len(s)-(b-a)):
         if b-a > 9 and fp[a-1] != fp[i]:
            continue
         dict = {}
         s2 = s[i:i+(b-a)+1]
         for i in range(b-a+1):
            if s2[i] not in dict:
               if s1[i] in dict.values(): break
               dict[s2[i]] = s1[i]
            if dict[s2[i]] != s1[i]: break
         else:
            k += 1
      ret.append(k)

   return ret

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

อินพุต

"hjhhbcbk", [(1,2), (2,4)]

ผลลัพธ์

[6, 1]