## KHUYÊN CÁC BẠN NÊN SUY NGHĨ TRƯỚC KHI ĐỌC SOLUTION NHAAA
nói thật bài này khó phần cài hơn phần tư duy :) Dễ thiếu trường hợp và dễ lẫn nhiều chỗ...
## Kiến thức cần
- Trie (tất nhiên)
- So khớp chuỗi (Hash,...)
## Ý tưởng
- Gọi $A$ thứ nhất $B$ là xâu thứ 2. Để $A + B$ là palindrome, ta chia 3 trường hợp:
- (Gọi $B'$ là xâu ngược của xâu $B$, gọi $A'$ là xâu ngược của xâu $A$)
- **_TH1 : $|A| = |B|$_**
- Ở trường hợp này đơn giản là toàn bộ xâu $A$ phải đối xứng với toàn bộ xâu $B$.
- Nói cách khác, $A + B$ là palindrome khi $A' = B$
- **_TH2 : $|A| < |B|$_**
- Trường hợp này cần 2 điều kiện để $A + B$ là xâu đối xứng.
- $|A|$ ký tự cuối của $B$ phải đối xứng với $A$, phần dư còn lại $B[1..|B|-|A|]$ bản thân nó phải là 1 palindrome
- Hoặc $A = B'[1..|A|]$ và $B[1..|B|-|A|] - B'[|A|+1..|B|]$
- **_TH3 : $|A| > |B|$_**
- Ta có thể suy ra công thức của trường hợp này như trường hợp 2, chỉ ngược lại
- $A[1..|B|] = B'$ và $A[|B|+1..|A|] = A'[1..|A|-|B|]$
Mình biết cái đống điều kiện đó hơi rối mắt 😅, trust me, hiểu được 3 trường hợp là xong ý tưởng rồi.
## Cách cài
Có thể dễ biết bước đầu tiên là đưa mọi xâu vào cây Trie, để biết một node cần lưu thông tin gì thì... từ từ :)
- Bây giờ mới tới phần khó là truy vấn :v Mình sẽ phân tích cách tính từng trường hợp. Ở đây là mình đang truy vấn cho xâu $B$ số lượng xâu $A$ mà $A + B$ là palindrome
- **_TH1 : $|A| = |B|$_**
- Cái này thì nhiều cách tính, mình thì đơn giản lưu tất cả xâu $A$ vào 1 cái map rồi truy vấn bằng xâu $B'$
- Lưu ý 1 trường hợp là xâu $A$ chính nó có thể là palindrome nên để tránh đếm dư thì -1 nếu $A$ là palindrome
- **_TH2 : $|A| < |B|$_**
- $|A| < |B|$ nghĩa là $B$ sẽ đi sâu hơn trên Trie so với $A$.
- Mình đi xuống Trie theo xâu $B'$ thay vì $B$. Nếu đi qua một node đánh dấu kết thúc của một xâu $A$
ta có thể thấy điều kiện đầu tiên đã được đáp ứng, đó là toàn bộ xâu $A$ khớp với phần đầu của $B'$
- Nhưng ta chưa thể tăng biến kết quả được vì điều kiện 2, đó là phần còn lại của $B'$ có là palindrome hay không
- Để kiểm tra ta có thể dùng hashing để kiểm tra tính đối xứng phần còn lại của $B'$. Nếu khớp thì ta tăng biến đếm bằng số lượng xâu A kết thúc tại đây.
- **_TH3 : $|A| > |B|$_**
- $|A| > |B|$ đồng nghĩa việc mình đã đi hết $B'$ và đếm hết những **TH2** nhưng vẫn có khả năng đếm thiếu do còn những xâu tiềm năng $A$ dài hơn mà có khả năng ghép với $B$.
- Bạn có thể thấy điều kiện đầu tiên đã được đáp ứng sẵn. Gọi đỉnh $P$ là đỉnh đánh dấu kết thúc xâu $B'$.
Những xâu $A$ mà có phần đầu khớp với $B'$ đều nằm trong cây con đỉnh $P$.
- Điều kiện còn lại là phần dư của những xâu $A$ bản thân phải là palindrome, tức phần cây con của $P$ trừ đỉnh $P$.
- Ta có thể thêm một giá trị vào Trie $cntSufPal[P]$ là câu trả lời cho "Có bao nhiêu xâu đi qua đỉnh $P$, và phần còn lại là một palindrome (không kể ký tự tại $P$)".
- Ta hoàn toàn có thể tính trước mảng này khi đang thêm một xâu vào Trie, dùng hash để kiểm tra tính đối xứng.
- Vậy Trie của ta sẽ lưu:
- cntSufPal : Số xâu đi qua đỉnh $P$, và phần còn lại là một palindrome (không kể ký tự tại $P$)
- cnt : Số xâu có điểm kết thúc tại đây
thế thôi :>
## [END]
kevinPhan
Created at
1 likes