Chương trình tìm chỉ số các chuỗi con khớp hoàn toàn hoặc khác một vị trí trong Python

Giả sử chúng ta được cung cấp hai chuỗi. Chuỗi đầu tiên có độ dài lớn hơn chuỗi thứ hai, và chúng ta phải kiểm tra xem các chuỗi con từ chuỗi đầu tiên có khớp chính xác với chuỗi thứ hai hay khác biệt ở một vị trí. Chúng ta trả về các chỉ số của chuỗi đầu tiên, nơi các chuỗi con có thể khớp với chuỗi thứ hai bắt đầu.

Ví dụ, nếu đầu vào là string1 = 'tpoint', string2 = 'pi', thì đầu ra sẽ là 1 2.

Các chuỗi con từ chuỗi đầu tiên khớp với chuỗi thứ hai hoặc khác một vị trí tại chỉ số 1 và 2 lần lượt là 'po' và 'oi'.

Thuật toán giải quyết

Để giải quyết bài toán này, chúng ta thực hiện các bước sau:

1. Định nghĩa hàm search() nhận vào string1 và string2:
   • Ghép chuỗi: str_cat := string1 + string2
   • Khởi tạo mảng Z z_list kích thước str_cat với giá trị 0
   • Thiết lập z_list[0] := độ dài của str_cat
   • Khởi tạo right := 0, left := 0
   • Duyệt i từ 1 đến độ dài str_cat:
     • Nếu i > right: mở rộng thủ công từ vị trí i
     • Ngược lại: tận dụng thông tin đã tính toán trong khoảng [left, right]
     • Cập nhật z_list[i] := min(độ dài string1, z_list[i])
   • Trả về phần của z_list từ chỉ số độ dài string1 đến cuối
2. Tính fwd := search(str2, str1) (chuỗi thứ hai so với chuỗi thứ nhất)
3. Tính bwrd := search(đảo ngược str2, đảo ngược str1) rồi đảo ngược kết quả
4. Duyệt các vị trí bắt đầu có thể của chuỗi con trong str1:
   • Nếu fwd[i] + bwrd[i + len(str2) - 1] >= len(str2) - 1 thì thêm chỉ số i vào kết quả
5. Trả về danh sách chỉ số hoặc False nếu không tìm thấy

Ví dụ minh họa

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'))

Đầu vào

'tpoint', 'pi'

Đầu ra

1 2