โปรแกรมค้นหาสตริงย่อยของสตริงที่กำหนดในตำแหน่งที่กำหนดในชุดของสตริงย่อยที่เป็นไปได้ทั้งหมดใน python

สมมติว่าเราได้รับจำนวนสตริงจำนวน n; str1, str2, str3,.....,strn. ทีนี้ สมมติว่า substri เป็นเซตที่มี substring ทั้งหมดของ stri ยูเนียนของเซตย่อยทั้งหมดคือ substr_union ตอนนี้เราได้รับจำนวนการสืบค้น q และเราต้องหาองค์ประกอบที่ q-th ของชุด substr_union ชุด substr_union ถูกจัดเรียงตามพจนานุกรมและดัชนีเริ่มต้นจาก 1

ดังนั้น หากอินพุตเหมือนกับรายการสตริงคือ =['pqr', 'pqt'] เคียวรีคือ =[4, 7, 9] ผลลัพธ์จะเป็น ['pqt', 'qt', 't' ]

สตริงย่อยจากสตริงแรกคือ subs_str_1 ={p, pq, pqr, q, qr, r }, sub_str_2 ={p, pq, pqt, q, qt, t}.

ยูเนี่ยนของสองชุดนี้หรือ substr_union คือ {p, pq, pqr, pqt, q, qr, qt, r, t}.

ดังนั้นรายการที่ดัชนี 4, 7 และ 9 คือ 'pqt', qt' และ 't' ตามลำดับ

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

• กำหนดฟังก์ชัน lng_i() นี้จะใช้เวลาพอ, lng, i
  • d :=ทูเพิลใหม่ที่มี (suff, lng)
  • หล่อ :=0
  • สวัสดี :=0
  • สำหรับแต่ละทูเพิล (suf, lng) ใน d ทำ
    • ถ้า lng คล้ายกับ null แล้ว
      • lng :=0
    • hi :=hi + ขนาดของ suf - lng
    • ถ้า hi - 1 เหมือนกับ i แล้ว
      • ส่งคืน suf
    • มิฉะนั้น เมื่อ hi - 1> i แล้ว
      • สำหรับดัชนี p และรายการ q ในรายการค่าตั้งแต่ lng ถึงขนาดของ suf ให้ทำ
        • ถ้า lo + p เหมือนกับ i แล้ว
          • คืนค่า suf[จากดัชนี 0 ถึง j+1]
    • หล่อ :=สวัสดี
  • คืนค่าเท็จ
• กำหนดฟังก์ชัน hlp_ii() นี่จะใช้เวลา str1,str2
  • ub :=ขนาดต่ำสุดของ str1 , ขนาดของ str2
  • cnt :=0
  • สำหรับผมในช่วง 0 ถึง ub ให้ทำ
    • ถ้า str1[i] เหมือนกับ str2[i] แล้ว
      • cnt :=cnt + 1
    • มิฉะนั้น
      • คืนสินค้า
    • คืนสินค้า
• t_dict :=แผนที่ใหม่
• suff :=รายการใหม่
• lng :=รายการใหม่
• สำหรับแต่ละ str ในสตริง ทำ

  • สำหรับฉันในช่วง 0 ถึงขนาดของ str ทำ

    • value :=str[จากดัชนี i ถึงจุดสิ้นสุด]
    • หากไม่มีค่าใน t_dict แล้ว
      • t_dict[value] :=1
      • ใส่ค่าที่ส่วนท้ายของ suff
• จัดเรียงรายการต่อท้าย
• suff_len :=ขนาดของ suff
• สำหรับฉันในช่วง 0 ถึงขนาดของ suff_len ทำ
  • ถ้าฉันเหมือนกับ 0 แล้ว
    • ใส่ null ที่ส่วนท้ายของ lng
  • มิฉะนั้น
    • แทรก hlp_ii(suff[i-1], suff[i]) ต่อท้าย lng
• res :=รายการใหม่
• สำหรับแต่ละ q ใน q_list ทำ
  • แทรก (lng_i(suff, lng, q-1)) ที่ส่วนท้ายของความละเอียด
• ผลตอบแทน

ตัวอย่าง

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

def lng_i(suff, lng, i):
   d = zip(suff,lng)
   lo = hi = 0
   for suf, lng in d:
      if lng is None:
         lng = 0
      hi += len(suf) - lng
      if hi - 1 == i:
         return suf
      elif hi - 1 > i:
         for p, q in enumerate(list(range(lng, len(suf)))):
            if lo + p == i:
               return suf[:q+1]
      lo = hi
   return False

def hlp_ii(str1,str2):
   ub = min(len(str1), len(str2))
   cnt = 0
   for i in range(ub):
      if str1[i] == str2[i]:
         cnt += 1
      else:
         return cnt
   return cnt

def solve(strings,q_list):
   t_dict = {}
   suff = []
   lng = []
   for str in strings:
      for i in range(len(str)):
         value = str[i:]
         if value not in t_dict:
            t_dict[value] = 1
            suff.append(value)
   suff.sort()
   suff_len = len(suff)
   for i in range(suff_len):
      if i == 0:
         lng.append(None)
      else:
         lng.append(hlp_ii(suff[i-1], suff[i]))
   res = []
   for q in q_list:
      (res.append(lng_i(suff, lng, q-1)))
   return res

print(solve(['pqr', 'pqt'], [4, 7, 9]))

อินพุต

['pqr', 'pqt'], [4, 7, 9]

ผลลัพธ์

['pqt', 'qt', 't']