โปรแกรมหาดัชนีที่ซับสตริงตรงกันทั้งหมดหรือต่างกันที่ตำแหน่งเดียวใน Python

สมมติว่าเรามีสตริงสองตัว สตริงแรกมีความยาวมากกว่าสตริงที่สอง และเราต้องตรวจสอบว่าซับสตริงจากสตริงแรกตรงกับสตริงที่สองทุกตัวอักษร หรือต่างกันเพียงตำแหน่งเดียว เราจะคืนค่าดัชนีของสตริงแรกที่ซับสตริงเหล่านั้นเริ่มต้น

เช่น ถ้าอินพุตคือ string1 = 'tpoint', string2 = 'pi' ผลลัพธ์จะเป็น 1 2

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

ขั้นตอนการแก้ปัญหา

1. สร้างฟังก์ชัน search() ที่รับ string1 และ string2
2. รวมสตริง: str_cat = string1 + string2
3. สร้าง Z-array (z_list) ขนาดเท่า str_cat เริ่มต้นด้วย 0
4. ตั้งค่า z_list[0] = len(str_cat), left = 0, right = 0
5. วนลูป i จาก 1 ถึง len(str_cat) - 1:
   • ถ้า i > right: คำนวณ Z-value แบบตรงไปตรงมาโดยเปรียบเทียบตัวอักษร
   • ถ้า i <= right: ใช้ค่า Z ที่คำนวณไว้ก่อนหน้าเพื่อเพิ่มประสิทธิภาพ
   • จำกัดค่า Z ให้ไม่เกินความยาวของ string1

ตัวอย่างโค้ด

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 not idx:
        return False
    return " ".join(idx)

print(solve('tpoint', 'pi'))  # Output: 1 2

อินพุต

'tpoint', 'pi'

เอาต์พุต

1 2