Ксоня та алфавітне коло#93

Ксоня та алфавітне коло (Editorial)

Рядок «алфавітний», якщо кожна наступна літера йде в алфавіті одразу після попередньої. Зверніть увагу, що перехід z a алфавітним не вважається — у прикладі рядок zab відкинуто.

Літери розташовані на колі, тому шуканий підрядок може «перевалюватися» через кінець масиву. Стандартний прийом для кола — пройтися по подвоєному масиву: розглянемо індекси від до 2n - 1 і працюватимемо з символом s[i \bmod n].

Тепер задача стала лінійною: знайти найдовший відрізок, у якому кожен наступний символ на одиницю більший за попередній за кодом. Це один прохід зі лічильником: якщо s[(i+1) \bmod n] дорівнює наступній за s[i \bmod n] літері, збільшуємо поточну довжину, інакше скидаємо її в одиницю. Відповідь — максимум цього лічильника.

Дві важливі деталі. По-перше, довжину треба обмежити зверху числом : обійшовши коло, ми не маємо права рахувати ті самі позиції двічі. По-друге, відповідь ніколи не перевищує , бо літери в алфавітному рядку строго зростають, а їх усього .

Складність — . Розв'язок, що явно будує всі поворотів кола, має складність \mathcal{O}(n^2) і при n = 10^4 вже помітно повільніший.