Editorial for Bedao Mini Contest 14 - CONFESSION


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Gọi ~S_i~ là ký tự thứ ~i~ từ trái sang của xâu ~S~ ~(1 \le i \le n)~, vậy xâu đối xứng là một xâu thỏa mãn ~S'_i~ = ~S'_{n-i+1}~ ~\forall~ ~(1 \le i \le n)~ và ta cần tìm các điều kiện để tạo được ~S'~ là một xâu đối xứng.

Điều kiện #1~:~ Ta chỉ được phép đổi chỗ các ký tự trong đoạn tiền tố độ dài ~k~ của xâu ~S,~ vậy với mọi chỉ số ~i~ thỏa mãn ~k+1 \le i \le n-k~ thì cả ~S_i~ và ~S_{n-i+1}~ đều không bị ảnh hưởng bởi thao tác đổi chỗ. Nói cách khác~,~ để ~S'~ là xâu đối xứng thì đoạn con ~S_{k+1}, \ldots, S_{n-k}~ phải tạo thành một xâu đối xứng.

Điều kiện #2~:~ Trong trường hợp tồn tại cách xếp thì tiền tốhậu tố độ dài ~k~ của xâu ~S~ phải là hoán vị của nhau, ta có thể áp dụng nhận xét sau để kiểm tra : cho ~A~ và ~B~ là ~2~ xâu có cùng độ dài~,~ gọi ~A'~ là xâu thu được khi xếp các ký tự trong ~A~ theo thứ tự không giảm và tương tự ta cũng có ~B'~, dễ thấy ~A~ và ~B~ là hoán vị của nhau khi và chỉ khi ~A' = B'~.

Độ phức tạp để kiểm tra ~2~ điều kiện trên là ~O(n)~ hoặc ~O(n*log(n))~ tùy cách cài đặt.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.