Функцiя вiд рядка#91

Функцiя вiд рядка (Розбір)

Підрядків у рядка довжини 10^5 близько 5 \cdot 10^9 — перебирати їх неможливо. Потрібна структура, що групує однакові за поведінкою підрядки; класичний вибір — суфіксний автомат.

Що дає суфіксний автомат. Побудований за автомат має станів, і кожен його стан — це цілий клас підрядків із однаковою множиною позицій закінчень (endpos). Для стану :

  • усі підрядки класу мають однакову кількість входжень — це , позначимо ;

  • їхні довжини утворюють проміжок, найбільша з них — .

Звідси головне спостереження: у межах одного класу вигідно брати найдовший підрядок, бо множник спільний. Отже

\max_{s} f(s) \;=\; \max_{v \ne \text{корінь}} \ \mathrm{len}(v) \cdot \mathrm{cnt}(v),

і замість мільярдів підрядків перебираємо лише станів.

Як порахувати . Під час побудови позначаємо \mathrm{cnt} = 1 для кожного стану, створеного як «основний» при додаванні чергового символу (клоновані стани отримують ). Далі значення проштовхуємо вниз суфіксними посиланнями: \mathrm{cnt}(\mathrm{link}(v)) \mathrel{+}= \mathrm{cnt}(v). Робити це треба в порядку спадання — суфіксні посилання завжди ведуть у стан із меншим , тож такий порядок гарантує, що до моменту обробки його власне значення вже остаточне. Порядок отримуємо сортуванням підрахунком за — , без sort.

Далі один прохід по станах і максимум добутку. Не забудьте, що відповідь сягає |T| \cdot |T| = 10^{10}, — потрібен -бітний тип.

Перевірка на прикладі. Для T = \t{aaaaaa} підрядок aaa трапляється чотири рази, тож f = 3 \cdot 4 = 12; aa дає 2 \cdot 5 = 10, а aaaa — 4 \cdot 3 = 12. Максимум — , як і в умові.

Складність — \mathcal{O}(|T| \cdot \Sigma) часу й пам'яті (\Sigma = 26), або \mathcal{O}(|T| \log \Sigma), якщо переходи тримати в map. Ту саму задачу розв'язує й суфіксний масив із масивом LCP плюс стек, але автомат помітно коротший.