Xử lý tiền tố trong một tập các xâu là một trong những vấn đề thường được đề cập trong các bài toán xử lý xâu. Trong nhiều trường hợp, cấu trúc cây tiền tố [Trie] được coi là một giải pháp hiệu quả.
Bản chất của cấu trúc Trie là một cây có gốc. Bản thân gốc không chứa thông tin, nhưng mỗi cạnh nối 2 nút trên cây tương ứng với 1 ký tự; do đó đường đi từ nút gốc tới một nút bất kỳ trên cây này cho biết tập đang xét có chứa xâu tiền tố biểu diễn bởi tập các cạnh thể hiện đường đi từ nút gốc tới nút đang đề cập đến.
Ví dụ như với cây ở trên, đường đi từ nút 1 tới nút 7 đại diện cho xâu tiền tố “bg”, đường đi từ nút 1 đến nút 10 đại diện cho xâu tiền tố “acd”.
Ta nhận thấy, từ mỗi nút, sẽ chỉ có tối đa 1 cạnh tỏa tới một nút khác mà đem theo ký tự c bất kỳ. Nói cách khác, giả sử trên cây này ta muốn lưu thêm 1 xâu “bgh” vào, thì khi xuất phát từ nút 1, ta sẽ không vẽ thêm một cạnh mới chứa ký tự ‘b’ mà sử dụng cạnh chứa ký tự ‘b’ đã có tỏa ra từ nút 1, và đi tới nút 3. Tương tự, ta sử dụng tiếp cạnh 3-7 để tới nút 7, lưu ký tự ‘g’. Tới đây, từ nút 7 không có cạnh nào tỏa ra mà mang theo ký tự ‘h’, ta sẽ vẽ thêm cạnh này, và đích đến của nó sẽ là 1 nút mới [để việc đánh số thứ tự nút liền mạch, ta sẽ coi như nút mới có số thứ tự 11].
Trong một số trường hợp, ta sẽ nảy sinh tình huống là không thể biết được đâu là điểm kết thúc xâu. Ví dụ như với cây mới này, ta không thể biết được liệu có xâu “bg” trong tập hợp không, hay “bg” chỉ đơn giản là tiền tố của xâu “bgh” vừa thêm vào. Bởi vậy, mỗi nút có thêm 1 thuộc tính boolean nữa, cho biết nút tương ứng có phải điểm kết thúc của một xâu hay không.
Hiển nhiên, ở một bước bất kỳ nào, tất cả các nút lá có trên cây sẽ đều mang trạng thái có.
Có 3 thao tác chính có thể thực hiện với cây Trie:
- Thêm một xâu S vào cây. Độ phức tạp là O[|S|].
- Xóa một xâu S khỏi cây. Độ phức tạp cũng là O[|S|]. Lưu ý rằng, khi xóa một xâu, để biết có thể loại bỏ cạnh nào và không loại bỏ cạnh nào [ở đây giả sử mọi xâu trong tập hợp đều đôi một khác nhau], ta cần phải biết các tiền tố của S có phải là các xâu đang có trong tập hợp không. Lúc này, thuộc tính boolean đề cập ở trên sẽ có giá trị trong việc theo dõi đặc tính này.
- Kiểm tra xem một xâu S có tồn tại trong tập hợp dưới dạng một xâu hoàn chỉnh hoặc một tiền tố hay không. Độ phức tạp của phép kiểm tra này cũng chỉ là O[|S|], và việc dùng Trie đơn giản hơn so với cây nhị phân tìm kiếm [Binary Search Tree – BST] cân bằng rất nhiều [nếu không có thư viện sẵn có thì việc cài đặt BST và giữ nó ổn định vô cùng phức tạp].
Bài toán tham khảo: P176PROC – ROUND 6C – GOOD OR BAD? [SPOJ – PTIT]
Phương pháp: Đây là một bài toán mà phương pháp làm nó đúng như đề bài yêu cầu: kiểm tra lần lượt từng xâu, nếu có xâu không thỏa mãn thì ngừng ngay chương trình ở điểm đó, và in ra “thủ phạm”.
Với 10^5 xâu [độ dài xâu không quá 60 ký tự], việc kiểm tra tiền tố có thể dễ dàng được thực hiện bằng Trie, và thực tế có thể thực hiện ngay khi điền thêm thông tin của xâu mới vào cây Trie.
Nguyên tắc khi làm việc này sẽ là: ta đặt hai biến boolean, “newRoad” và “endString”, trước khi bắt đầu thực hiện điền xâu, đều khởi tạo là false.
- “newRoad” sẽ trở thành “true” khi ở một điểm nào đó của xâu, ta không có đường đi cũ để dùng lại mà phải vẽ ra đường đi mới và tạo nút mới cho cây.
- “endString” sẽ trở thành “true” khi ta đi qua bất kỳ nút nào đại diện cho điểm kết thúc của một xâu [trong trường hợp này là khi đi qua nút lá, vì nếu có một nút nào đó không phải lá lại là điểm kết thúc xâu thì hiển nhiên chương trình đã phải kết thúc từ trước đó!]
Sau mỗi quá trình, nếu [newRoad = true] và [endString = false] tức là xâu đang xét không phải là tiền tố của bất kỳ xâu nào, hoặc không có xâu nào đã điền trước đó là tiền tố của xâu đang xét, nên ta có thể tiếp tục bài toán.
Ngược lại, thì xâu đang xét sẽ là xâu đầu tiên vi phạm nguyên tắc đề bài. Lúc này ta in ra “BAD SET” cùng với xâu đó và kết thúc chương trình.
Độ phức tạp: O[K*N] [K là độ dài tối đa của xâu trong input, ở đây K