Словник префіксів і суфіксів#374

Словник префіксів і суфіксів (Розбір)

Автор задачі:

Олександр Тимкович

Задачу підготував:

Павло Ціцей

Розбір написав:

Павло Ціцей

Ми можемо сконструювати слово , якщо всі літери в є принаймні в деякому слові серед a_i для всіх .

Покажімо, чому це правда. Ми знаємо, що підрядок є суфіксом деякого префікса (для підрядка з до ви можете взяти префікс з до , а потім суфікс з до ), тому якщо нам потрібна якась літера в , ми знаходимо її в a_i, записуємо її префікс, де остання літера потрібна, а потім беремо суфікс довжини . Якщо ми зробимо це для всіх літер, які нам потрібні, ми отримаємо слова з літери, які можуть конструювати слово по одній літері.