| Một chuỗi được gọi là Palindrome nếu sau khi đảo ngược các ký tự của nó, ta nhận được chuỗi ban đầu. Ví dụ. chuỗi "MADAM" là Palindrome. Viết chương trình nhập rồi xác định xem một chuỗi có phải là Palindrome hay không Em code thế này sao cứ chạy là báo lỗi. Em không biết chỗ nào sai. Bác nào có code thì up lên giùm em tham khảo luôn nhé. Cảm ơn 
Tree Palindrome (hay còn được gọi là Eertree), được phát minh bởi Mikhail Rubinchik, là một loại dữ liệu cấu trúc cấu trúc được sử dụng để giải một số bài toán liên quan đến 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 cấp để kết 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ó thể xếp 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 phải là 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, tiền tố không tầm thường (hậu tố thích hợp) là tiền tố của một xâu và ngắn hơn thứ hạng đó). Từ bây giờ ta sẽ gọi palindrome lớn nhất mà là tiền 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 chuỗi 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 nhịp độ dài -1 thì ta sẽ được xếp nhịp độ dài 1 và nó luôn là palindrome. Gốc thứ hai chứa một xâu trống (xâu có độ dài bằng 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 chuỗi palindrome vào nút khi cài đặt thực tế, nếu làm như vậy ta sẽ tốn quá nhiều bộ nhớ. Nút thực tế sẽ bao gồm chiều dài xâu chuỗi palindrome, chữ cái được gán cho các cung và các liên kết hậu tố Ở đây mình sẽ hướng dẫn tạo cây Palindrome chứa tất cả các con palindrome của một xâu s. Ta thấy. Một nhịp độ dài $n$ sẽ không có quá $n$ nhịp palindrome con, vì vậy cây Palindrome sẽ không có quá $n$ + 2 nút (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 save back $t$ is palindrom sut suat to tien tien tien $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ờ chúng ta hãy tìm palindrom tiền tố hậu tố 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 bất kỳ đó, có thể làm trố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ả cá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à palindrome hậu tố lớn nhất của $p + x$, nên tất cả các palindrome hậu tố đều 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ố nào của palindrome 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 . Sau đó ta kiểm tra xem có cung cấp nào được gán chữ $x$ tương ứng với nút chứa chuỗi $A$, nếu không, thêm một cung được gán chữ $x$ nối từ nút chứa chuỗi $A$ đến nút chứa mới Bây giờ chúng ta hãy xem xét các liên kết nối hậu tố từ nút $xAx$. Nếu nút này đã có từ trước, thì nút này đã có các liên kết thuận lợi và ta không phải làm gì cả. Nếu không, ta cần phải tìm palindrome có ưu điểm lớn nhất của $xAx$, có dạng $xBx$, mà $B$ là một xâu có thể rỗng. Bằng chứng lập luận tương tự như trên, $B$ là palindrome hậu tố của $p$ và có thể được lấy từ $t$ bằng các liên kết hậu tố Vì vậy ta đã 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 tiền tố lớn nhất $t$ của tiền tố đã xử lí (khởi tạo $t$ là xâu). 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 palindrome hậu tố 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ố để khi tìm thấy chuỗi palindrome $B$, có thể thêm được hai chữ $x$ ở hai bên, sau đó ta thêm các liên kết hậu tố từ nút Để biết thêm thông tin chi tiết, bạn có thể tham khảo mã. (bạn không cần chú ý đến biến $num$ vì nó được thêm vào để giải bài toán cụ thể). Bạn có thể thấy mã không quá dài cũng như việc cài đặt rất đơn giản The process too build a Palindrome tree for a length $n$. Ta thấy rằng khi ta xử lý từng chữ cái một, đầu của liên kết hậu tố palindrome lớn nhất của tiền tố được xử lý luôn luôn chuyển sang bên phải. Do đó, mức độ phức tạp của việc xây dựng cây Palindrome là $O(n)$ Dem number palindrom xuất hiện thêmbài toán. Cho thêm chữ cái $x$ vào cuối xâu $S$, đếm số lượng palindrome xuất hiện thêm trong xâu $S$. Ví dụ khi ta cho thêm chữ cái a vào cuối xâu aba, ta có thêm một palindrome nữa là aa Rõ ràng lời giải thích là rõ ràng. Ta xây dựng cây Palindrome cho xâu $S$ ban đầu, và với mỗi chữ cái mới được thêm vào, ta biết được số palindrome mới xuất hiện thêm bằng cách đếm số nút vừa được tạo ra trên cây Palindrome. Lưu ý. palindrome number output current more after add one letter into a chain by 1 or by 0 Đếm số lượng xâu con liên tiếp là palindromeMã giải bài này bằng cây Palindrome đã có ở trên. Bài toán này còn có thể giải bằng thuật toán Manachar, tuy vậy ta nên giải bằng cây Palindrome vì cây Palindrome còn có thể ứng dụng cho nhiều bài toán khác |
