Tìm mẫu trong chuỗi và xử lý các lần khớp chồng nhau

Lan cần tìm mã ana trong chuỗi banana. Nếu chỉ đếm mỗi lần xuất hiện không chồng nhau, Lan sẽ bỏ sót một vị trí. Với một triệu ký tự, thử lại toàn bộ mẫu tại từng vị trí còn có thể tốn quá nhiều phép so sánh.

Chuỗi con phải gồm các ký tự liên tiếp

Chuỗi con (substring) gồm các ký tự nằm liên tiếp trong chuỗi gốc. Dãy con (subsequence) giữ nguyên thứ tự nhưng có thể bỏ qua ký tự. Chuỗi ana xuất hiện hai lần trong banana, bắt đầu ở chỉ số 1 và 3.

Hai lần xuất hiện dùng chung ký tự ở chỉ số 3. Chúng được gọi là khớp chồng nhau (overlapping matches). Phương thức count của Python không đếm các lần chồng nhau:

text = "banana"
pattern = "ana"
print(text.count(pattern))
positions = []
for i in range(len(text) - len(pattern) + 1):
    if text[i:i + len(pattern)] == pattern:
        positions.append(i)
print(positions)

1
[1, 3]

Vòng lặp thử từng vị trí hợp lệ, kể cả vị trí nằm trong lần khớp trước. Với chuỗi dài n và mẫu dài m, cách thử từng lát có thể tốn O(nm) thời gian. Nếu n = 100000 và m = 10000, số ký tự phải so có thể lên tới khoảng một tỉ.

Một dãy con không nhất thiết là chuỗi con. Ta duyệt chuỗi nguồn và chỉ tiến con trỏ mẫu khi gặp ký tự đang cần:

text = "banana"
pattern = "bnn"
j = 0
for ch in text:
    if j < len(pattern) and ch == pattern[j]:
        j += 1
print(j == len(pattern))

True

Mỗi ký tự nguồn được xét một lần. Do đó, cách này tốn O(n) thời gian và O(1) bộ nhớ phụ. Dãy con rỗng luôn được nhận vì con trỏ đã ở cuối mẫu ngay từ đầu.

Chỉ số giúp mô tả chính xác đoạn cần lấy

Lát cắt s[l:r] lấy từ chỉ số l đến trước r. Khi hai đầu bằng nhau, kết quả là chuỗi rỗng. Với nhãn vimic, hãy chạy các phép lấy đoạn sau:

s = "vimic"
print(s[1:4])
print(s[:2])
print(repr(s[3:3]))
print(s[-2:])

imi
vi
''
ic

Lát đầu gồm các chỉ số 1, 2 và 3. repr giúp bạn nhìn thấy chuỗi rỗng. Chỉ số âm tính từ cuối, nên lát cuối lấy hai ký tự cuối.

split() không có đối số tách theo các cụm khoảng trắng và bỏ khoảng trắng hai đầu. Ngược lại, strip() chỉ bỏ khoảng trắng biên, không thay khoảng trắng giữa các từ.

line = "  an   binh  "
print(repr(line.strip()))
words = line.split()
print(words)
print(" ".join(words))

'an   binh'
['an', 'binh']
an binh

Ghép lại bằng một dấu cách tạo kết quả chỉ có một khoảng trắng giữa các từ. Chỉ dùng phép chuẩn hóa này nếu đề cho phép thay đổi khoảng trắng.

find trả vị trí bắt đầu của lần xuất hiện đầu tiên hoặc -1 nếu không thấy. startswith và endswith kiểm tra hai đầu chuỗi. Các phép này phân biệt chữ hoa và chữ thường.

code = "vimic-python"
print(code.find("python"))
print(code.find("java"))
print(code.startswith("vimi"))
print(code.endswith("Python"))

6
-1
True
False

find không liệt kê mọi vị trí chồng nhau. Khi cần tất cả, hãy chọn quét hoặc KMP theo giới hạn dữ liệu.

Hàm tiền tố ghi nhớ phần đầu cũng là phần cuối

Với một chuỗi, tiền tố (prefix) là đoạn bắt đầu từ đầu chuỗi. Hậu tố (suffix) là đoạn kết thúc ở cuối chuỗi. Tiền tố thực sự phải ngắn hơn toàn bộ đoạn đang xét.

Với ababa, chuỗi aba vừa là tiền tố vừa là hậu tố. Độ dài 3 là lớn nhất trong các tiền tố thực sự có tính chất này. Mảng pi lưu kết quả tương tự cho từng đoạn kết thúc tại mỗi chỉ số:

Đoạn abab có tiền tố và hậu tố chung dài nhất là ab, dài 2. Đoạn ababa có giá trị 3. Bảng trên thử mọi độ dài để minh họa, không phải cách xây bảng nhanh.

Khi thêm ký tự s[i], trước tiên ta thử nối nó vào tiền tố dài pi[i-1]. Nếu không khớp, tiền tố ứng viên tiếp theo có độ dài pi[j-1]. Ta lặp lại cho đến khi khớp hoặc độ dài về 0.

def prefix_function(s):
    pi = [0] * len(s)
    for i in range(1, len(s)):
        j = pi[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

print(prefix_function("ababa"))
print(prefix_function("aaaa"))
print(prefix_function(""))

[0, 0, 1, 2, 3]
[0, 1, 2, 3]
[]

Tại mỗi bước lùi, phần đang xét vẫn là hậu tố đã khớp và cũng là tiền tố của mẫu. Không thể bỏ qua một ứng viên dài hơn: mọi ứng viên còn lại phải là hậu tố của phần đã khớp. Tổng số lần tăng và giảm j là O(m), nên tính bảng dài m tốn O(m) thời gian và bộ nhớ.

Theo dõi một lần lùi trong bảng tiền tố

Xét chuỗi ababaca. Trước ký tự c, đoạn ababa có tiền tố chung dài nhất là aba, nên j = 3. Ký tự tiếp theo của tiền tố là b, khác c.

Phần có thể giữ lại phải là hậu tố của aba và cũng là tiền tố của chuỗi. Bảng cho ứng viên kế tiếp dài pi[2] = 1, tức a. Ký tự sau a vẫn là b, khác c.

Ta tiếp tục lùi về pi[0] = 0. Ký tự a cũng khác c, nên giá trị tại c bằng 0. Ký tự a cuối cùng khớp với ký tự đầu, nên giá trị cuối bằng 1.

Hãy chạy chương trình để kiểm tra toàn bộ bảng:

s = "ababaca"
pi = [0] * len(s)
for i in range(1, len(s)):
    j = pi[i - 1]
    while j and s[i] != s[j]:
        j = pi[j - 1]
    if s[i] == s[j]:
        j += 1
    pi[i] = j
print(pi)

[0, 0, 1, 2, 3, 0, 1]

j vừa là độ dài phần đã khớp, vừa là chỉ số ký tự tiếp theo cần so. Khi j = 0, không đọc pi[j-1] để lùi nữa.

KMP dùng bảng tiền tố để tránh so lại

Thuật toán Knuth–Morris–Pratt (KMP) giữ j là số ký tự đầu của mẫu đang khớp với phần cuối đã đọc. Khi ký tự mới không khớp, bảng tiền tố cho biết có thể giữ lại bao nhiêu ký tự. Con trỏ trong văn bản không cần quay lại.

Hàm sau yêu cầu mẫu không rỗng. Đề bài cần quy định riêng ý nghĩa của mẫu rỗng:

def prefix_function(s):
    pi = [0] * len(s)
    for i in range(1, len(s)):
        j = pi[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

def find_all(text, pattern):
    if not pattern:
        raise ValueError("Mẫu phải khác rỗng")
    pi = prefix_function(pattern)
    found = []
    j = 0
    for i, ch in enumerate(text):
        while j > 0 and ch != pattern[j]:
            j = pi[j - 1]
        if ch == pattern[j]:
            j += 1
        if j == len(pattern):
            found.append(i - len(pattern) + 1)
            j = pi[j - 1]
    return found

print(find_all("banana", "ana"))
print(find_all("aaaaa", "aaa"))
print(find_all("abc", "abcd"))

[1, 3]
[0, 1, 2]
[]

Sau mỗi lần khớp đầy đủ, j = pi[j-1] giữ hậu tố còn có thể bắt đầu lần khớp tiếp theo. Nếu đặt j = 0, chương trình bỏ sót các lần chồng nhau. Tiền xử lý và tìm kiếm tốn O(n + m) thời gian. Bộ nhớ phụ là O(m) ngoài danh sách kết quả.

Với n = 1000000 và m = 10000, tổng độ dài chỉ là 1010000 ký tự. KMP thực hiện số bước tỷ lệ với tổng này, thay vì thử lại tới một tỉ ký tự. Số bước cụ thể phụ thuộc dữ liệu và cách cài đặt.

Nếu mẫu dài hơn văn bản, không thể có lần khớp đầy đủ. Nếu mẫu chỉ có một ký tự, mỗi ký tự nguồn trùng mẫu tạo một kết quả. Mẫu rỗng cần được đề quy định riêng.

Một số thư viện coi mẫu rỗng xuất hiện ở mọi ranh giới giữa các ký tự. Hàm find_all ở trên từ chối mẫu rỗng.

Sau mỗi ký tự văn bản, j là độ dài tiền tố dài nhất của mẫu khớp với hậu tố phần văn bản đã duyệt. Khi hai ký tự kế tiếp khác nhau, ứng viên dài hơn không thể tiếp tục.

Mỗi ký tự nguồn làm j tăng nhiều nhất một lần. Mỗi bước lùi giảm j ít nhất một. Tổng số lần lùi bị chặn bởi tổng số lần tăng, nên cả lượt quét vẫn tuyến tính.

Ví dụ sau đọc văn bản và mẫu không rỗng từ hai dòng. Chương trình chỉ đếm nên dùng O(m) bộ nhớ phụ cho bảng, thay vì lưu mọi vị trí:

abababa
aba

s = input()
p = input()
pi = [0] * len(p)
for i in range(1, len(p)):
    j = pi[i - 1]
    while j and p[i] != p[j]:
        j = pi[j - 1]
    if p[i] == p[j]:
        j += 1
    pi[i] = j
count = 0
j = 0
for ch in s:
    while j and ch != p[j]:
        j = pi[j - 1]
    if ch == p[j]:
        j += 1
    if j == len(p):
        count += 1
        j = pi[j - 1]
print(count)

3

Chuỗi bất biến nên cần chọn cách xây kết quả

Chuỗi Python là bất biến (immutable): không thể thay trực tiếp một ký tự bằng phép gán chỉ số. Ví dụ sau cố tình gây lỗi:

name = "Lan"
name[0] = "N"

TypeError: 'str' object does not support item assignment

Bạn có thể tạo danh sách ký tự, sửa danh sách rồi nối lại. Với nhiều mảnh cần ghép, join cho biết rõ chương trình tạo một chuỗi kết quả:

letters = list("Lan")
letters[0] = "N"
print("".join(letters))
print("-".join(["lop", "python", "22"]))

Nan
lop-python-22

Không nên giả định mọi ký tự có thể ánh xạ bằng ord(ch) - ord('a'). Công thức đó phù hợp khi đề bảo đảm chữ cái thường từ a đến z. Với tập ký tự khác, một dict hoặc Counter biểu diễn tần suất trực tiếp:

from collections import Counter
counts = Counter("ba na")
print(counts["a"])
print(counts[" "])

2
1

Để kiểm tra một chuỗi có đọc xuôi và ngược giống nhau, hãy so chuỗi với bản đảo ngược. Cách này xét cả dấu cách và phân biệt chữ hoa, chữ thường:

for word in ["radar", "python", "a"]:
    print(word, word == word[::-1])

radar True
python False
a True

Nếu đề bỏ qua dấu cách hoặc chữ hoa, chương trình phải chuẩn hóa dữ liệu trước khi so. Phép tạo bản đảo ngược tốn O(n) thời gian và O(n) bộ nhớ cho chuỗi dài n.

Hậu tố đối xứng giúp nối thêm ít ký tự

Giả sử nhãn abac cần trở thành chuỗi đối xứng bằng cách chỉ thêm ký tự vào cuối. Phần ở cuối chuỗi gốc có thể giữ lại phải tự đối xứng. Với ví dụ này, hậu tố đối xứng dài nhất là c; ta nối ngược phần còn lại là aba.

Để tìm hậu tố đó bằng bảng tiền tố, đặt rev = s[::-1]. Ghép rev + "#" + s, với dấu # không xuất hiện trong s. Một tiền tố của chuỗi ghép cũng là hậu tố của nó tương ứng với một hậu tố đối xứng của s.

Vì sao? Tiền tố độ dài k của rev là bản đảo của hậu tố độ dài k của s. Nếu hai phần này bằng nhau thì hậu tố đó đọc xuôi và ngược giống nhau. Dấu phân cách ngăn phần trùng dài hơn chuỗi ban đầu.

s = "abac"
combined = s[::-1] + "#" + s
pi = [0] * len(combined)
for i in range(1, len(combined)):
    j = pi[i - 1]
    while j and combined[i] != combined[j]:
        j = pi[j - 1]
    if combined[i] == combined[j]:
        j += 1
    pi[i] = j
longest = pi[-1]
added = s[:len(s) - longest][::-1]
print("Số ký tự thêm:", len(added))
print("Nhãn mới:", s + added)

Số ký tự thêm: 3
Nhãn mới: abacaba

Hậu tố đối xứng dài nhất giữ lại nhiều ký tự nhất. Mỗi ký tự đứng trước hậu tố phải có một bản đối xứng ở phần được thêm. Vì vậy không thể thêm ít hơn số ký tự của phần đầu còn lại.

Chuỗi ghép dài 2n + 1, nên tính bảng tốn O(n) thời gian và bộ nhớ. Với 10000 ký tự, bảng có 20001 ô. Dấu phân cách phải khác mọi ký tự đầu vào.

Tổng tiền tố trả lời nhiều câu hỏi về ký tự

Giả sử cần đếm chữ a trong nhiều đoạn của banana. Quét từng đoạn đủ tốt khi chỉ có một câu hỏi nhỏ. Nếu có nhiều đoạn dài, các ký tự bị quét lại nhiều lần.

Bài 12 giới thiệu tổng tiền tố. Ở đây mỗi chữ a đóng góp 1, còn ký tự khác đóng góp 0. Đặt pref[k] là số chữ a trong k ký tự đầu.

Với đoạn chỉ số từ l đến r tính cả hai đầu, đáp án là pref[r+1] - pref[l]. Phần bị trừ gồm đúng l ký tự đứng trước đoạn. Ví dụ sau nhận các đoạn đánh số từ 1:

s = "banana"
pref = [0]
for ch in s:
    pref.append(pref[-1] + (ch == "a"))
for l, r in [(2, 4), (1, 6)]:
    print(pref[r] - pref[l - 1])

2
3

Đoạn 2 đến 4 gồm ana, còn đoạn 1 đến 6 là toàn bộ chuỗi. Tính bảng tốn O(n) thời gian và bộ nhớ. Sau đó mỗi truy vấn tốn O(1).

Nếu n = 100000 và có 10000 truy vấn, tổng số bước tỷ lệ khoảng 110000. Quét lại mọi đoạn có thể xét gần một tỉ ký tự. Con số thực tế tùy độ dài các đoạn.

Đo cách ghép và chọn công cụ phù hợp

Chuỗi bất biến nên nối lặp có thể tạo nhiều chuỗi trung gian. Một số bản Python tối ưu riêng phép +=; số đo không phải bảo đảm cho mọi môi trường. Gom các mảnh rồi dùng join khi xây kết quả dài.

Đoạn sau đo hai cách trên cùng dữ liệu và kiểm tra kết quả giống nhau. Thời gian phụ thuộc máy đang chạy và không dùng làm ngưỡng chấm điểm.

from time import perf_counter
parts = ["ab"] * 10000
start = perf_counter()
s = ""
for part in parts:
    s += part
loop_time = perf_counter() - start
start = perf_counter()
t = "".join(parts)
join_time = perf_counter() - start
print("Giống nhau:", s == t)
print("Nối lặp, giây:", round(loop_time, 6))
print("join, giây:", round(join_time, 6))

Giống nhau: True
Nối lặp, giây: 0.001438
join, giây: 2.5e-05

Kết quả thời gian có thể thay đổi giữa các lần chạy. Hãy kiểm tra tính đúng trước khi so tốc độ. Nếu cần sửa nhiều vị trí, bạn có thể sửa một list rồi ghép một lần.

Lỗi thường gặp

Tóm tắt

• Chuỗi con liên tiếp; dãy con giữ thứ tự nhưng có thể bỏ ký tự.
• count đếm các lần không chồng nhau. KMP có thể tìm toàn bộ vị trí chồng nhau.
• pi[i] là độ dài tiền tố thực sự dài nhất cũng là hậu tố của đoạn kết thúc tại i.
• KMP mất O(n + m) thời gian và O(m) bộ nhớ phụ ngoài kết quả.
• Chuỗi bất biến; join nối các mảnh và Counter đếm ký tự không cần giả định bảng chữ cái.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về chuỗi, gồm count và join.
• Bài giảng KMP của Đại học Concordia, phân tích số phép so sánh.
• Tài liệu Python về collections.Counter, đếm các phần tử theo giá trị.