Kinky Letters Movement#12832

Kinky Letters Movement (Editorial)

Максим Щерба

Якщо з рядка за чотири операції можна одержати рядок s_2, то існує послідовність операцій s_1 \to a \to b \to c \to s_2. З рядка s_1 можна одержати рядок за дві операції. Оскільки перевертання підрядка — оборотна операція, то з рядка s_2 також можна одержати рядок за дві операції. Задача звелася до того, що потрібно перевірити, чи існує такий рядок , що його можна одержати за дві операції з s_1 і s_2.

Утворимо всі можливі рядки двома перевертаннями підрядка з s_1, обчислимо поліноміальний геш для кожного з них та додамо їх у геш-таблицю (unordered_set у C++). Далі утворимо таким же чином рядки з s_2 та перевіримо, чи є в геш-таблиці такий рядок.

Можливих рядків, які можна одержати за дві операції з s_1 є O(|s_1|^4), для кожного з них обчислюємо геш за O(|s_1|). Складність такого розв'язку: O(|s_1|^5).