bvd
user-avatar

Bùi Việt Dũng

Đóng góp: 46

Ngày sinh: 06/12/2000

Đăng ký: 05/07/2015

Lần đăng nhập cuối: 23/12/2016

Kết nối tài khoản

VOJ: bvdung (2.13 điểm)

Topcoder: Chưa kết nối

Cây Palindrome

Mình không phải là người phát minh ra cấu trúc dữ liệu này. Mình chỉ đọc blog của Mikhail Rubinchik và giới thiệu lại với mọi người thôi :)

Bài viết này sẽ mô tả cây Palindrome, một loại cấu trúc dữ liệu tuyệt vời được dùng để giải một số bài toán liên quan đến Palindrome. Loại cấu trúc dữ liệu này khá là mới, thậm chí bây giờ Google "cây Palindrome" bạn cũng không có thông tin gì về nó đâu. Theo như mình biết, tên cây Palindrome nó cũng không phải là tên chính thức của cấu trúc dữ liệu này (vì nó thậm chí cũng không phải là cây).

Update #1: Tên chính thức của cấu trúc dữ liệu này là Eertree, các bạn có thể tìm hiểu thêm về nó tại đây.

Trong bài viết này mình vẫn dùng tên cây Palindrome vì tên đó nghe hay hơn.

Cấu trúc của cây Palindrome

Như mọi loại cây khác, cây Palindrome cũng có nút.

Ngoài nút ra cây còn có các cung để nối các nút. Cung nối giữa hai nút u và v được gán một chữ cái - ví dụ chữ X - nghĩa là ta có được palindrome chứa ở nút v bằng cách thêm chữ X vào hai bên của palindrome chứa ở nút u.

Trong ví dụ trên, ta có được xâu palindrome aba bằng cách thêm chữ a vào hai bên chữ b

Cuối cùng, ta có thêm các liên kết hậu tố. Nút u có liên kết hậu tố đến nút w, nếu palindrome chứa ở nút w là hậu tố không tầm thường lớn nhất của palindrome chứa ở nút u. (hậu tố là một xâu con chứa các chữ cái cuối cùng của xâu, hậu tố không tầm thường (proper suffix) là hậu tố của một xâu và ngắn hơn xâu đó). Từ bây giờ ta sẽ gọi palindrome lớn nhất mà là hậu tố không tầm thường của một xâu là palindrome hậu tố lớn nhất của một xâu.

Trong ví dụ trên, vì a là palindrome hậu tố lớn nhất của aba nên có một liên kết hậu tố từ nút chứa xâu aba đến nút chứa xâu a.

Đặt tên cấu trúc dữ liệu này là cây Palindrome có vẻ không hợp lí lắm, vì nó có tận 2 gốc. Một sẽ chứa xâu palindrome giả độ dài -1. Gốc này giúp ta cài đặt cây dễ dàng hơn, vì khi ta thêm hai chữ cái bất kì vào hai bên xâu độ dài -1 thì ta sẽ được xâu độ dài 1 và nó luôn là palindrome. Gốc thứ hai chứa một xâu rỗng (xâu có độ dài 0), và xâu này cũng là palindrome. Ta cho thêm một liên kết hậu tố từ hai gốc nối đến gốc chứa palindrome độ dài -1.

Lưu ý rằng ta không chứa xâu palindrome vào nút khi cài đặt thực tế, nếu làm vậy ta sẽ tiêu tốn quá nhiều bộ nhớ. Nút thực tế sẽ chứa độ dài xâu palindrome, chữ cái được gán vào các cung, và các liên kết hậu tố.

Xây dựng cây Palindrome

Ở đây mình sẽ hướng dẫn tạo cây Palindrome chứa tất cả các palindrome con của một xâu s. Ta thấy: Một xâu độ dài n sẽ không có quá n xâu palindrome con, vì vậy cây Palindrome sẽ không có quá n + 2 nút (do phải thêm 2 gốc nữa).

Ta sẽ xử lí từng chữ cái một trong xâu. Giả sử ta đã xử lí được tiền tố p của xâu, và giờ ta phải xét đến chữ cái x tiếp theo.

Ta lưu lại t là palindrome hậu tố lớn nhất của tiền tố p.

Vì t đã được xử lí, nên nó được chứa trong một nút nào đó của cây Palindrome. Nút này sẽ có liên kết hậu tố đến một nút nào đó, nút nào đó lại có một liên kết hậu tố đến một nút khác và cứ tiếp tục như vậy.

Bây giờ ta hãy tìm hậu tố palindrome của tiền tố mới p+x. Hậu tố đó sẽ có dạng xAx, với A là một xâu nào đó, có thể rỗng hoặc có độ dài -1. Vì xAx là palindrome, nên A cũng là palindrome, và nó là một hậu tố của p, vì vậy ta có thể tìm A từ t bằng các liên kết hậu tố.

Xâu xAx sẽ là xâu palindrome con duy nhất của xâu p + x mà không xuất hiện ở xâu p. Thật vậy, ta thấy tất cả xâu palindrome con mới mà ta chưa thấy trong xâu p phải kết thúc bằng chữ x, và do đó trở thành hâu tố của xâu p + x. Vì xAx là hậu tố palindrome lớn nhất của p + x, tất cả các hậu tố palindrome nhỏ hơn nó có thể được tìm thấy trong một số tiền tố của xAx (vì đối với bất kì hậu tố của palindrome có một tiền tố tương tự tương ứng), và vì thế ta đã thấy chúng trong p.

Vì vậy, để xử lí chữ cái x thêm vào, ta phải đi theo các liên kết hậu tố của t cho đến khi ta tìm thấy A thích hợp (xâu A thích hợp có thể có độ dài -1 nếu ta phải đi đến gốc). Sau đó ta kiểm tra xem có cung nào được gán chữ x mà tương ứng với nút chứa xâu A, nếu không, thêm một cung được gán chữ x nối từ nút chứa xâu A đến nút mới chứa xâu xAx.

Bây giờ ta xét đến các liên kết hậu tố nối từ nút xAx. Nếu nút này đã có từ trước, nút này đã có các liên kết hậu tố và ta không phải làm gì cả. Nếu không, ta cần phải tìm palindrome hậu tố lớn nhất của xAx, có dạng xBx, mà B là một xâu có thể rỗng. Bằng lập luận tương tự như trên, B là palindrome hậu tố của p và có thể đến được từ t bằng các liên kết hậu tố.

Vậy ta đã có được thuật toán xây dựng cây Palindrome. Xử lí từng chữ cái một, lưu trữ palindrome hậu tố lớn nhất t của tiền tố đã xử lí (khởi tạo t là xâu rỗng). Khi xử lí thêm chữ x, ta phải đi qua các liên kết hậu tố xuất phát từ t, cho đến khi ta tìm được palindrome A thích hợp. Xâu xAx sẽ trở thành sẽ trở thành hậu tố palindrome lớn nhất và trở thành nút duy nhất có thể chèn vào cây. Để tạo thêm các liên kết hậu tố ta phải đi theo các liên kết hậu tố cho đến khi tìm thấy xâu palindrome B, có thể thêm được hai chữ x ở hai bên, rồi ta thêm liên kết hậu tố từ nút chứa xâu xAx đến xâu xBx.

Để biết thêm thông tin chi tiết, bạn có thể tham khảo code. (bạn không cần chú ý đến biến num vì nó được cho thêm vào để giải bài toán cụ thể). Bạn có thể thấy code không quá dài cũng như việc cài đặt rất đơn giản.

Độ phức tạp: O(n)

Ứng dụng

- Cho thêm chữ x vào cuối xâu, đếm số lượng palindrome xuất hiện thêm (bằng số nút được cho thêm vào cây Palindrome).

- Đếm số lượng palindrome trong xâu (code ở trên :) ). Bạn có thể dùng thuật toán Manachar để giải, tuy vậy ta nên dùng cây Palindrome vì nó tiện dụng hơn.

- Số lần xuất hiện của Palindrome trong xâu (ngoài cây Palindrome bạn có thể dùng Hash).

Bài tập để luyện tập

Bài 1, Bài 2

Codeforces Round #342 (Div 2)

Vào 16:05 chiều nay 07/02/2016 Codeforces Round #342 (Div 2) sẽ diễn ra. Round này lấy đề từ Kì thi chọn Học sinh Giỏi THCS Quốc gia Nga năm nay.

Thời gian kết thúc đăng kí đã hết

Mọi người có thể cùng vào đây thảo luận sau khi cuộc thi kết thúc.

COCI 2015/2016 #5

Em đăng hộ anh iamquang95 (hình như sau VOI anh ấy quên) :D

Vào 21:00  tối nay 16/01/2016 COCI #5 sẽ diễn ra

Đề thì sẽ gồm 6 bài theo kiểu oi trong thời gian 3 tiếng đồng hồ.

Mọi người có thể cùng vào đây thảo luận sau khi cuộc thi kết thúc.

Đáp án VOI 2011

Đang lục lọi thư viện trường thấy cái này, share cho mọi người tham khảo (thấy tiếp sẽ đăng tiếp tại topic này)

Hóa ra Bộ cũng có đáp án chính thức

http://www.mediafire.com/view/34470dbh0m6iybd/Dap_an_de_HSGQG_nam_2011_mon_Tin_hoc_ngay_1.pdf

http://www.mediafire.com/view/m8ez642w86tn90v/Dap_an_de_HSGQG_nam_2011_mon_Tin_hoc_ngay_2.pdf

Tiện thể cho em hỏi: Thế này duyệt + tham + quy hoạch động trực tiếp + nhớ các thuật toán cơ bản với độ phức tạp \(O(n^3)\) là đã được khoảng 20 điểm = giải Ba rồi ạ (năm đó giải Ba 18 điểm thì phải?). Điều này có còn đúng với các năm sau nữa không.

Cho mình hỏi các unit này có được sử dụng khi thi không?

Cho mình hỏi các unit AvgLvlTree, URadixSort, ... và một số unit khác đã có sẵn thuật toán trong FPC, chỉ cần mình khai báo đúng kiểu là dùng được thì có được sử dụng khi thi không?

Mình nghĩ #include <algothrim> dùng được thì chắc mấy thư viện này cũng dùng được :)
Nếu dùng được thì không biết C++ có cái nào tương tự không nhỉ?

Mình hiểu các khái niệm (về BST) này có đúng không vậy?

Cho cây sau:

Khi ta duyệt theo thứ tự giữa:

1, Nút liền trước của nút 3 là nút -4, nút liền trước của nút -4 là 2 phải không? (đã tự giải đáp được rồi :( )

2, Sau khi xóa nút 2 thì nút -4 sẽ lên thay thế nút 2 phải không?

3, Trong thuật toán tìm nút liền trước, không gặp nút nào chứa x trong nhánh con phải thì nó là nút cực trái phải không (câu này cũng đã dùng thực tế kiểm chứng được rồi)

4,

{
Dòng có // là những phần mình định thay thế, thêm vào.
Dòng {} {dùng để hỏi
Code gốc lấy từ quyển 2 "Tài liệu giáo khoa chuyên Tin"
}
function Predecessor(x: PNode): PNode;
// var y,yp: PNode;
begin
  // y:=x;
  if x^.left ≠ nilT then
  Result := Maximum(x^.left)
  else
  repeat
    //yp:=y;
    Result := x^.parent; // thay thế bằng y:=y^.parent; 
    if (Result = nilT) or (x = Result^.right) then Break; // Đoạn này mình sẽ thay thế Result = y, x = yp
    x := Result; {Lệnh này có sai không vậy, sao không cần var x: PNode mà vẫn chạy được?}
  until False;
  // Result:=y;
end;

5, Sao các thuật toán về cây trong sách "Tài liệu giáo khoa chuyên Tin" đều không dùng đệ quy vậy? (phải đặt lại bộ nhớ Stack chăng?)
Khi nào cần hỏi gì nữa thì mình sẽ hỏi tiếp ở topic này nhé :)
Xin cảm ơn trước!