Вірус#157

Вірус (Editorial)

Мутований вірус — це рядок , у якому змінено рівно два символи, причому відстань між ними дорівнює саме . Отже, підрядок s[i \ldots i+n-1] підходить тоді й лише тоді, коли він відрізняється від рівно у двох позиціях та p+k.

Перевіряти кожну позицію наївним порівнянням коштувало б \mathcal{O}(|s| \cdot n) — забагато. Натомість скористаємось прийомом «швидко знайти перше неспівпадіння».

Порахуємо поліноміальні хеші префіксів обох рядків. Тоді за можна порівняти будь-який підрядок з будь-яким підрядком рівної довжини. А маючи таке порівняння, першу позицію розбіжності між та знаходимо двійковим пошуком за \mathcal{O}(\log n): шукаємо найдовший спільний префікс.

Алгоритм для кожної стартової позиції такий:

  1. знайти першу розбіжність — нехай це позиція (якщо розбіжностей немає, підрядок збігається з повністю, а це не мутація — потрібно рівно дві зміни);

  2. перевірити, що позиція p + k теж не виходить за межі та теж є розбіжністю;

  3. перевірити, що між і p+k та після p+k до кінця розбіжностей більше немає — це ще два порівняння підрядків через хеші;

  4. якщо все виконалось, позиція підходить.

Загальна складність — \mathcal{O}(|s| \log n), що з запасом вкладається в обмеження.

У першому рядку виводимо кількість знайдених входжень, у другому — їхні початкові індекси за зростанням. Не забудьте про випадок, коли входжень немає: другий рядок тоді порожній.

Порада щодо надійності: беріть достатньо великий простий модуль (або два різні модулі), щоб уникнути колізій хешів.