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