Khóa học Python từ Cơ bản đến Nâng cao

Bài 5.3. Bài tập Python: tìm đoạn con

Chào mừng các bạn quay trở lại với series học Python! Trong bài học này, chúng ta sẽ cùng nhau khám phá một bài toán khá phổ biến và thú vị: tìm kiếm đoạn con trong một chuỗi (string) hoặc một danh sách (list). Đây là một kỹ năng cơ bản nhưng cực kỳ quan trọng, xuất hiện trong rất nhiều ứng dụng thực tế, từ xử lý văn bản, phân tích dữ liệu cho đến các thuật toán phức tạp hơn.

Bạn đã bao giờ cần kiểm tra xem một từ cụ thể có xuất hiện trong một đoạn văn dài hay không? Hay bạn muốn tìm vị trí của một chuỗi dữ liệu nhỏ bên trong một tập dữ liệu lớn hơn? Đó chính là lúc kỹ thuật tìm kiếm đoạn con phát huy tác dụng!

Hãy cùng đi sâu vào chi tiết và xem Python cung cấp cho chúng ta những công cụ mạnh mẽ nào để giải quyết vấn đề này nhé!

"Đoạn con" là gì?

Trước tiên, chúng ta cần định nghĩa rõ ràng “đoạn con” là gì.

Trong ngữ cảnh của bài viết này, đoạn con (có thể gọi là substring đối với chuỗi hoặc subarray đối với danh sách/mảng) là một chuỗi các phần tử liên tiếp nằm bên trong một chuỗi hoặc danh sách lớn hơn.

• Ví dụ với chuỗi:
  • Chuỗi gốc: "Lập trình Python"
  • Các đoạn con hợp lệ: "Lập", "trình", "Python", "trình Py", " ", "Lập trình Python" (chính nó cũng là đoạn con).
  • Không phải đoạn con (vì không liên tiếp): "Lập Python"
• Ví dụ với danh sách:
  • Danh sách gốc: [10, 20, 30, 40, 50]
  • Các đoạn con hợp lệ: [20, 30], [10], [30, 40, 50], [10, 20, 30, 40, 50]
  • Không phải đoạn con (vì không liên tiếp): [10, 30, 50]

Bây giờ, hãy xem cách chúng ta có thể tìm kiếm những đoạn con này bằng Python.

Tìm đoạn con trong Chuỗi (Substring)

Làm việc với chuỗi là một trong những thế mạnh của Python. Ngôn ngữ này cung cấp nhiều cách tiện lợi để tìm kiếm substring.

1. Kiểm tra sự tồn tại với toán tử in

Cách đơn giản nhất để biết một chuỗi có chứa một chuỗi con khác hay không là sử dụng toán tử in. Nó sẽ trả về True nếu tìm thấy và False nếu không.

main_string = "Chào mừng bạn đến với thế giới lập trình Python!"
substring = "Python"
substring_khong_co = "Java"

# Kiểm tra xem 'Python' có trong chuỗi chính không
if substring in main_string:
    print(f"Tìm thấy '{substring}' trong chuỗi.")
else:
    print(f"Không tìm thấy '{substring}' trong chuỗi.")

# Kiểm tra xem 'Java' có trong chuỗi chính không
if substring_khong_co in main_string:
    print(f"Tìm thấy '{substring_khong_co}' trong chuỗi.")
else:
    print(f"***Không tìm thấy '{substring_khong_co}' trong chuỗi.***")

• Giải thích:
  • Dòng if substring in main_string: sử dụng toán tử in để kiểm tra xem toàn bộ chuỗi substring ("Python") có xuất hiện ở bất kỳ đâu bên trong main_string hay không.
  • Kết quả là một giá trị boolean (True hoặc False), quyết định nhánh nào của câu lệnh if-else sẽ được thực thi.
  • Đây là cách kiểm tra sự tồn tại nhanh và dễ đọc nhất.

2. Tìm vị trí xuất hiện đầu tiên: find() và index()

Nếu bạn không chỉ muốn biết đoạn con có tồn tại hay không mà còn muốn biết vị trí bắt đầu của nó (chỉ số index), bạn có thể dùng phương thức find() hoặc index().

• find(substring): Trả về chỉ số index của vị trí bắt đầu vý hiện đầu tiên của substring. Nếu không tìm thấy, nó trả về -1.
• index(substring): Tương tự find(), nhưng nếu không tìm thấy substring, nó sẽ ném ra một lỗi ValueError thay vì trả về -1.

main_string = "Học Python để lập trình Python hiệu quả."
substring = "Python"
substring_khong_co = "Ruby"

# Sử dụng find()
vi_tri_find = main_string.find(substring)
print(f"Sử dụng find(): '{substring}' xuất hiện lần đầu tại index {vi_tri_find}") # Output: 4

vi_tri_khong_co_find = main_string.find(substring_khong_co)
print(f"Sử dụng find(): '{substring_khong_co}' xuất hiện lần đầu tại index {vi_tri_khong_co_find}") # Output: -1

# Sử dụng index()
try:
    vi_tri_index = main_string.index(substring)
    print(f"Sử dụng index(): '{substring}' xuất hiện lần đầu tại index {vi_tri_index}") # Output: 4
except ValueError:
    print(f"Sử dụng index(): Không tìm thấy '{substring}'")

try:
    vi_tri_khong_co_index = main_string.index(substring_khong_co)
    print(f"Sử dụng index(): '{substring_khong_co}' xuất hiện lần đầu tại index {vi_tri_khong_co_index}")
except ValueError:
    print(f"***Sử dụng index(): Không tìm thấy '{substring_khong_co}'. Đã xảy ra ValueError!***")

# Tìm kiếm từ một vị trí cụ thể
vi_tri_thu_hai = main_string.find(substring, vi_tri_find + 1) # Bắt đầu tìm từ index sau vị trí đầu tiên
print(f"Sử dụng find() lần nữa: '{substring}' cũng xuất hiện tại index {vi_tri_thu_hai}") # Output: 24

• Giải thích:
  • main_string.find(substring) tìm "Python" trong chuỗi. Nó tìm thấy ở index 4 (ký tự 'P' đầu tiên).
  • main_string.find(substring_khong_co) tìm "Ruby". Không thấy nên trả về -1.
  • main_string.index(substring) cũng tìm thấy "Python" ở index 4.
  • Khi main_string.index(substring_khong_co) được gọi, vì "Ruby" không có trong chuỗi, một ValueError xảy ra. Chúng ta dùng try...except để bắt lỗi này và in ra thông báo thân thiện.
  • find() và index() có thể nhận tham số thứ hai là start, chỉ định vị trí bắt đầu tìm kiếm. Ví dụ main_string.find(substring, vi_tri_find + 1) tìm kiếm "Python" bắt đầu từ index 5 (ngay sau lần xuất hiện đầu tiên), và tìm thấy nó ở index 24.

3. Tìm tất cả các vị trí xuất hiện

Nếu bạn muốn tìm tất cả các vị trí mà đoạn con xuất hiện, bạn cần dùng vòng lặp kết hợp với find().

main_string = "ababababa"
substring = "aba"
vi_tri = []
start_index = 0

while True:
    # Tìm 'aba' bắt đầu từ start_index
    index = main_string.find(substring, start_index)

    # Nếu không tìm thấy (find trả về -1), dừng vòng lặp
    if index == -1:
        break

    # Nếu tìm thấy, thêm index vào danh sách kết quả
    vi_tri.append(index)

    # Cập nhật vị trí bắt đầu cho lần tìm kiếm tiếp theo
    # Chỉ cần dịch đi 1 là đủ để tìm các đoạn con gối nhau (overlapping)
    # Nếu muốn tìm các đoạn không gối nhau, dùng: start_index = index + len(substring)
    start_index = index + 1

if vi_tri:
    print(f"'{substring}' được tìm thấy tại các vị trí (index): {vi_tri}") # Output: [0, 2, 4, 6]
else:
    print(f"Không tìm thấy '{substring}' trong chuỗi.")

• Giải thích:
  • Chúng ta khởi tạo start_index = 0 để bắt đầu tìm từ đầu chuỗi.
  • Vòng lặp while True sẽ chạy liên tục cho đến khi gặp lệnh break.
  • main_string.find(substring, start_index) tìm substring từ vị trí start_index.
  • Nếu find trả về -1 (không tìm thấy nữa), vòng lặp kết thúc.
  • Nếu tìm thấy tại index, chúng ta thêm index vào danh sách vi_tri.
  • Quan trọng: start_index = index + 1 cập nhật vị trí bắt đầu cho lần lặp tiếp theo. Bằng cách chỉ tăng start_index lên 1, chúng ta cho phép tìm các đoạn con gối lên nhau. Ví dụ, trong "ababababa", "aba" đầu tiên ở index 0, lần tìm tiếp theo bắt đầu từ index 1, vẫn có thể tìm thấy "aba" bắt đầu ở index 2. Nếu bạn muốn tìm các đoạn con không gối nhau, bạn sẽ cập nhật start_index = index + len(substring).

Tìm đoạn con trong Danh sách (Subarray)

Việc tìm kiếm subarray trong list hoặc tuple phức tạp hơn một chút vì không có phương thức find() hay index() tích hợp sẵn như đối với chuỗi. Chúng ta thường phải tự cài đặt logic này.

Phương pháp lặp và cắt lát (Iteration and Slicing)

Đây là cách tiếp cận phổ biến nhất: duyệt qua danh sách gốc, tại mỗi vị trí, cắt ra một đoạn con có độ dài bằng đoạn con cần tìm và so sánh chúng.

def tim_vi_tri_subarray(main_list, sub_list):
    """
    Tìm vị trí bắt đầu của lần xuất hiện đầu tiên của sub_list trong main_list.
    Trả về index nếu tìm thấy, ngược lại trả về -1.
    """
    n = len(main_list)
    m = len(sub_list)

    # Nếu sub_list rỗng hoặc dài hơn main_list thì không thể tìm thấy
    if m == 0:
        return 0 # Coi như list rỗng là con của mọi list tại index 0
    if m > n:
        return -1

    # Duyệt qua các vị trí bắt đầu khả dĩ trong main_list
    # Chỉ cần duyệt đến n - m là đủ
    for i in range(n - m + 1):
        # Cắt ra một đoạn từ main_list có cùng độ dài với sub_list
        # Bắt đầu từ index i
        doan_con_hien_tai = main_list[i : i + m]

        # So sánh đoạn con vừa cắt với sub_list cần tìm
        if doan_con_hien_tai == sub_list:
            return i # Tìm thấy! Trả về vị trí bắt đầu i

    # Nếu duyệt hết vòng lặp mà không tìm thấy
    return -1

# Ví dụ sử dụng
data = [1, 2, 3, 4, 5, 6, 3, 4, 7]
can_tim = [3, 4]
khong_co = [5, 7]

vi_tri_1 = tim_vi_tri_subarray(data, can_tim)
print(f"Tìm thấy {can_tim} tại index: {vi_tri_1}") # Output: 2

vi_tri_2 = tim_vi_tri_subarray(data, khong_co)
print(f"Tìm thấy {khong_co} tại index: {vi_tri_2}") # Output: -1

list_rong = []
vi_tri_3 = tim_vi_tri_subarray(data, list_rong)
print(f"Tìm thấy {list_rong} tại index: {vi_tri_3}") # Output: 0

# Tìm tất cả các vị trí (cải tiến hàm trên hoặc viết hàm mới)
def tim_tat_ca_vi_tri_subarray(main_list, sub_list):
    vi_tri = []
    n = len(main_list)
    m = len(sub_list)
    if m == 0 or m > n:
        return vi_tri # Trả về list rỗng nếu không hợp lệ

    for i in range(n - m + 1):
        if main_list[i : i + m] == sub_list:
            vi_tri.append(i)
    return vi_tri

vi_tri_all = tim_tat_ca_vi_tri_subarray(data, can_tim)
print(f"Tìm thấy {can_tim} tại tất cả các index: {vi_tri_all}") # Output: [2, 6]

• Giải thích:
  • Hàm tim_vi_tri_subarray nhận vào danh sách chính main_list và danh sách con sub_list.
  • n và m là độ dài của hai danh sách.
  • Các điều kiện if m == 0 và if m > n xử lý các trường hợp đặc biệt.
  • Vòng lặp for i in range(n - m + 1): duyệt qua tất cả các chỉ số i mà tại đó một đoạn con có độ dài m có thể bắt đầu trong main_list. Lưu ý điểm dừng là n - m + 1 (không bao gồm) vì đoạn con cuối cùng bắt đầu tại n - m.
  • main_list[i : i + m] tạo ra một lát cắt (slice) của main_list từ chỉ số i đến i + m - 1. Đây chính là đoạn con tiềm năng.
  • if doan_con_hien_tai == sub_list: so sánh trực tiếp lát cắt này với sub_list. Nếu chúng bằng nhau, hàm trả về i.
  • Nếu vòng lặp kết thúc mà không tìm thấy sự trùng khớp nào, hàm trả về -1.
  • Hàm tim_tat_ca_vi_tri_subarray hoạt động tương tự, nhưng thay vì return i ngay khi tìm thấy, nó append(i) vào danh sách vi_tri và tiếp tục tìm kiếm cho đến hết, cuối cùng trả về danh sách vi_tri.

Lưu ý về hiệu suất: Phương pháp cắt lát và so sánh này khá dễ hiểu nhưng có thể không phải là tối ưu nhất cho các danh sách cực lớn, vì việc cắt lát và so sánh có thể tốn thời gian (độ phức tạp thường là O(n*m)). Có những thuật toán phức tạp hơn như KMP (Knuth-Morris-Pratt) hoặc Boyer-Moore có thể cải thiện hiệu suất đáng kể trong nhiều trường hợp, nhưng chúng nằm ngoài phạm vi của bài tập cơ bản này.

Tổng kết nhẹ

Qua bài này, chúng ta đã học được:

1. Khái niệm đoạn con (substring/subarray) là một chuỗi phần tử liên tiếp.
2. Cách kiểm tra sự tồn tại của substring trong string bằng toán tử in.
3. Cách tìm vị trí đầu tiên của substring bằng string.find() (trả về -1 nếu không thấy) và string.index() (ném ValueError nếu không thấy).
4. Cách tìm tất cả các vị trí của substring bằng cách lặp và sử dụng find() với tham số start.
5. Cách tìm vị trí subarray trong list bằng cách lặp qua các vị trí bắt đầu khả dĩ, cắt lát và so sánh.
6. Cách tìm tất cả các vị trí của subarray bằng cách điều chỉnh logic lặp và cắt lát.

Việc tìm kiếm đoạn con là một thao tác nền tảng. Hiểu và thực hành các kỹ thuật này sẽ giúp bạn tự tin hơn khi xử lý dữ liệu dạng chuỗi và danh sách trong Python. Hãy thử nghiệm với các ví dụ khác nhau để nắm vững kiến thức nhé!