โปรแกรมหาจำนวนคู่ซับสตริงที่เท่ากันใน Python

ได้รับสตริงสองตัว ต้องหาจำนวน quadruple (p,q,r,s) ที่:

1. 0 <= p <= q <= len(firstString)
2. 0 <= r <= s <= len(secondString)
3. ซับสตริง firstString[p:q+1] == secondString[r:s+1]
4. q - r น้อยที่สุดเท่าที่จะเป็นไปได้

ตัวอย่าง: firstString='hgfn', secondString='gfrt' ผลลัพธ์ 2 (คู่ (1,1,0,0) และ (2,2,1,1))

วิธีแก้ปัญหา

1. left[26] := infinity, right[26] := -1
2. บันทึกตำแหน่งแรกของแต่ละตัวอักษรใน firstString ลง left
3. บันทึกตำแหน่งสุดท้ายของแต่ละตัวอักษรใน secondString ลง right
4. หา mi := min(left[i] - right[i])
5. นับตัวอักษรที่ left[i] - right[i] == mi

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

def solve(firstString, secondString):
    left = [float('inf')] * 26
    right = [-1] * 26
    res = 0
    mi = float('inf')
    for i, ch in enumerate(firstString):
        left[ord(ch) - ord('a')] = min(left[ord(ch) - ord('a')], i)
    for i, ch in enumerate(secondString):
        right[ord(ch) - ord('a')] = max(right[ord(ch) - ord('a')], i)
    for i in range(26):
        if left[i] != -1:
            mi = min(mi, left[i] - right[i])
    for i in range(26):
        if left[i] != float('inf') and right[i] != -1:
            if left[i] - right[i] == mi:
                res += 1
    return res

print(solve('hgfn', 'gfrt'))

อินพุต

'hgfn', 'gfrt'

เอาต์พุต

2