Поза контекстом
Це той час року: сезон виборів. Політичні промови всюди, і ваш друг, диванний експерт, любить знаходити цитати політиків і використовувати їх поза контекстом. Ви хочете допомогти своєму другові, розробивши метод пошуку в тексті заданих шаблонів.
Один із найпотужніших способів виразити шаблон пошуку в тексті - це використання контекстно-вільної граматики (CFG). CFG використовується для генерації рядків і визначається як 4-кортеж (V, Σ, R, S), де V - це набір змінних, Σ - це набір термінальних символів, S V - це початкова змінна, а R - це набір правил. Кожне правило в R має вигляд
що вказує, що голова правила (змінна зліва від стрілки) може бути замінена, коли вона з'являється, на продукцію правила, послідовність змінних і термінальних символів на правій стороні стрілки. Можливо, що права сторона правила може бути порожньою. Це вказує, що змінна зліва може бути замінена на порожній рядок.
Граматика генерує рядок терміналів за допомогою процесу виведення. Виведення починається з послідовності, яка є лише початковою змінною. Потім, поки всі змінні не будуть видалені, ми повторно замінюємо будь-яку змінну в поточній послідовності на будь-яке з правил цієї змінної.
Як приклад, ось правила для граматики з початковою змінною A (зліва) і приклад виведення (справа).
Напишіть програму, яка може шукати в тексті підрядки, які могли бути згенеровані заданою CFG.
Вхідні дані
Для цієї задачі V - це набір великих літер англійського алфавіту, а Σ - це набір малих літер англійського алфавіту. Вхід починається з опису R, правил CFG. Перша строка містить ціле число 1 ≤ n ≤ 30, що вказує кількість правил, що слідують. Наступні n рядків описують одне правило у форматі
Тобто, велика літера, один пробіл, стрілка, один пробіл і рядок з нуля або більше великих чи малих літер. Продукції правил мають довжину не більше 10 символів. Початкова змінна S - це голова першого даного правила.
Після правил йде не більше 100 рядків тексту для пошуку, кожен довжиною не більше 50 символів. Кожен рядок вхідних даних складається лише з малих літер англійського алфавіту та пробілів. Вхід закінчується кінцем файлу.
Вихідні дані
Для кожного рядка для пошуку надрукуйте рядок, що дає найдовший непорожній підрядок, який граматика може згенерувати. Якщо є кілька найдовших, вкажіть підрядок, що з'являється найраніше в рядку. Якщо немає відповідного підрядка, надрукуйте NONE великими літерами.