Повнотекстовий пошук#3597
Містер Дон є адміністратором популярного сайту вікторин під назвою QMACloneClone. Користувачі можуть надсилати свої запитання до системи, а також шукати тексти запитань за довільними запитами. Ця система пошуку використовує метод біграмного пошуку.
Метод біграмного пошуку включає два етапи: попередню обробку та пошук.
Попередня обробка: Попередньо обчисліть множину всіх підрядків довжиною один або два символи для кожного тексту запитання.
Пошук: Обчисліть множину для рядка запиту таким же чином. Потім знайдіть тексти запитань, множини яких повністю містять множину, побудовану з запиту.
Все працювало добре деякий час після запуску функції. Однак один з користувачів виявив проблему: результати пошуку іноді містили запитання, які не включали рядок запиту в точному вигляді. Ці запитання навряд чи є тим, що користувачі хочуть. Тому Містер Дон почав розбиратися з проблемою і попросив вас про допомогу. Для кожного даного запиту на пошук ваше завдання — знайти довжину найкоротшого тексту запитання, вибраного методом біграм, який не містить рядка запиту як свого підрядка.
Вхід складається з кількох наборів даних. Набір даних подається як запит на пошук у кожному рядку. Вхід закінчується рядком, що містить лише знак решітки (), який не слід обробляти. Запит на пошук складається не більше ніж з символів та включає малі та/або великі літери. Тексти запитань і запити чутливі до регістру.
Для кожного запиту на пошук надрукуйте мінімально можливу довжину тексту запитання, що викликає проблему. Якщо такого тексту запитання немає, надрукуйте No Result в одному рядку (лапки лише для уточнення).
Приклад 1
Розглянемо ситуацію, коли текст запитання є "CloneQMAC". У цій ситуації множина, обчислена на етапі попередньої обробки, є \{\text{C}, \text{Cl}, \text{l}, \text{lo}, \text{o}, \text{on}, \text{n}, \text{ne}, \text{e}, \text{eQ}, \text{Q}, \text{QM}, \text{M}, \text{MA}, \text{A}, \text{AC}\}.
У тестовому випадку , наш вхідний текст (запит на пошук) є "QMAClone". Таким чином, множина, обчислена програмою на етапі пошуку, є \{\text{Q}, \text{QM}, \text{M}, \text{MA}, \text{A}, \text{AC}, \text{C}, \text{Cl}, \text{l}, \text{lo}, \text{o}, \text{on}, \text{n}, \text{ne}, \text{e}\}.
Оскільки перша множина містить усі елементи другої множини, текст запитання "CloneQMAC" вибирається програмою, коли запит на пошук є "QMAClone", хоча сам текст "CloneQMAC" не містить текст запиту "QMAClone". Крім того, ми можемо довести, що немає такого тексту довжиною менше , отже, очікуваний результат для цього запиту на пошук — .