Chương trình tìm số cặp chuỗi con bằng nhau trong Python

Mô tả bài toán

Cho hai chuỗi chữ thường. Tìm số bộ bốn (p, q, r, s) thỏa mãn:

• 0 <= p <= q <= len(firstString)
• 0 <= r <= s <= len(secondString)
• Chuỗi con firstString[p:q+1] == secondString[r:s+1].
• q - r nhỏ nhất có thể.

Ví dụ

Nếu firstString = 'hgfn', secondString = 'gfrt', đầu ra là 2 với các bộ (1,1,0,0) và (2,2,1,1).

Giải thuật

1. Với mỗi ký tự 'a'..'z', tìm vị trí đầu tiên xuất hiện trong firstString (left) và vị trí cuối cùng trong secondString (right).
2. Tìm mi = min(left[c] - right[c]) cho các ký tự xuất hiện ở cả hai chuỗi.
3. Đếm số ký tự có left[c] - right[c] == mi.

Triển khai Python

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] != float('inf'):
            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'))

Đầu vào

'hgfn', 'gfrt'

Đầu ra

2