โปรแกรมค้นหาดัชนีที่สตริงย่อยของสตริงตรงกับสตริงอื่นทั้งหมดหรือแตกต่างกันที่ตำแหน่งหนึ่งใน python

สมมติว่าเรามีให้สองสตริง สตริงแรกมีความยาวมากกว่าอันที่สอง และเราต้องตรวจสอบว่าสตริงย่อยจากสตริงแรกตรงกับสตริงที่สองหรือต่างกันในตำแหน่งเดียวหรือไม่ เราคืนค่าดัชนีของสตริงแรก โดยที่สตริงย่อยที่สามารถจับคู่กับสตริงที่สองเริ่มต้นได้

ดังนั้น หากอินพุตเป็นเหมือน string1 ='tpoint', string2 ='pi' ผลลัพธ์จะเป็น 1 2

สตริงย่อยจากสตริงแรกที่ตรงกับสตริงที่สองหรือแตกต่างกันในตำแหน่งเดียวที่ดัชนี 1 และ 2 คือ 'po' และ 'oi'

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

• กำหนดฟังก์ชัน search() นี่จะใช้เวลา string1, string2
  • str_cat :=string1 + string2
  • z_list :=รายการใหม่ของขนาดของ str_cat เริ่มต้นด้วย 0
  • z_list[0] :=ขนาดของ str_cat
  • ขวา :=0
  • ซ้าย :=0
  • สำหรับฉันในช่วง 1 ถึงขนาดของ str_cat ให้ทำ
    • ถ้าฉัน> ใช่แล้ว
      • j :=0
      • ในขณะที่ j + i <ขนาดของ str_cat และ str_cat[j] เท่ากับ str_cat[j+i] do
        • j :=j + 1
      • z_list[i] :=j
      • ถ้า j> 0 แล้ว
        • ซ้าย :=ฉัน
        • ขวา :=i + j - 1
    • มิฉะนั้น
      • k :=ผม - ซ้าย
      • r_len :=right - i + 1
      • ถ้า z_list[k]
      • z_list[i] :=z_list[k]
    • มิฉะนั้น
      • ม :=ขวา + 1
      • ในขณะที่ m <ขนาดของ str_cat และ str_cat[m] เท่ากับ str_cat[m - i] ทำ
        • ม :=ม + 1
        • z_list[i] :=m - i
        • ซ้าย :=ฉัน
        • ขวา :=ม. - 1
  • z_list[i] :=ขนาดต่ำสุดของ string1 , z_list[i]
• ส่งคืน z_list[จากขนาดดัชนีของ string1 ถึง end]

ตัวอย่าง

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

def search(string1, string2):
   str_cat = string1 + string2
   z_list = [0] * len(str_cat)
   z_list[0] = len(str_cat)
   right = 0
   left = 0
   for i in range(1, len(str_cat)):
      if i > right:
         j = 0
         while j + i < len(str_cat) and str_cat[j] == str_cat[j+i]:
            j += 1
         z_list[i] = j
         if j > 0:
            left = i
            right = i + j - 1
      else:
         k = i - left
         r_len = right - i + 1
         if z_list[k] < r_len:
            z_list[i] = z_list[k]
         else:
            m = right + 1
            while m < len(str_cat) and str_cat[m] == str_cat[m -i]:
               m += 1
            z_list[i] = m - i
            left = i
            right = m - 1
      z_list[i] = min(len(string1), z_list[i])
   return z_list[len(string1):]

def solve(str1, str2):
   fwd = search(str2, str1)
   bwrd = search(str2[::-1], str1[::-1])
   bwrd.reverse()
   idx = []
   for i in range(len(str1) - len(str2)+1):
      if fwd[i] + bwrd[i+len(str2)-1] >= len(str2)-1:
         idx.append(str(i))
   if len(idx) == 0:
      return False
   else:
      return (" ".join(idx))

print(solve('tpoint', 'pi'))

อินพุต

'tpoint', 'pi'

ผลลัพธ์

1 2