Kontekstdən kənar
Bu ilin o vaxtıdır: seçki mövsümü. Siyasi çıxışlar çoxdur və kreslo mütəxəssisi olan dostunuz siyasətçilərin sitatlarını kontekstdən çıxararaq istifadə etməyi sevir. Siz dostunuza mətn daxilində müəyyən edilmiş nümunələri axtarmaq üçün bir metod inkişaf etdirməklə kömək etmək istəyirsiniz.
Mətn axtarış nümunəsini ifadə etməyin daha güclü yollarından biri kontekstdən azad qrammatikadan (CFG) istifadə etməkdir. CFG sətirləri yaratmaq üçün istifadə olunur və 4-lü (V, Σ, R, S) kimi müəyyən edilir, burada V dəyişənlər dəstidir, Σ terminal simvollar dəstidir, S başlanğıc dəyişəndir və R qaydalar dəstidir. R-dəki hər bir qayda aşağıdakı formada olur:
Bu, qaydanın başlığının (oxun sol tərəfindəki dəyişən) oxun sağ tərəfindəki dəyişənlər və terminal simvollar ardıcıllığı ilə qaydanın istehsalı ilə əvəz edilə biləcəyini göstərir. Qaydanın sağ tərəfinin boş olması mümkündür. Bu, sol tərəfdəki dəyişənin boş sətirlə əvəz edilə biləcəyini göstərir.
Qrammatika terminal sətirini törəmə prosesi ilə yaradır. Törəmə yalnız başlanğıc dəyişəni olan bir ardıcıllıqla başlayır. Sonra, bütün dəyişənlər çıxarılana qədər, cari ardıcıllıqda istənilən dəyişəni həmin dəyişənin qaydalarından biri ilə təkrar-təkrar əvəz edirik.
Məsələn, başlanğıc dəyişəni A olan qrammatika üçün qaydalar (solda) və bir nümunə törəmə (sağda) verilmişdir.
Verilmiş CFG tərəfindən yaradılmış ola biləcək alt sətirləri mətn daxilində axtara bilən bir proqram yazın.
Giriş verilənləri
Bu problem üçün V İngilis böyük hərf əlifbası dəstidir və Σ İngilis kiçik hərf əlifbası dəstidir. Giriş CFG qaydalarının R təsviri ilə başlayır. İlk sətir ardınca gələcək qaydaların sayını göstərən 1 ≤ n ≤ 30 tam ədədini ehtiva edir. Növbəti n sətir hər biri bir qaydanı aşağıdakı formatda təsvir edir:
Yəni, böyük hərf, bir boşluq, bir ox, bir boşluq və sıfır və ya daha çox böyük və ya kiçik hərflərdən ibarət bir sətir. Qayda istehsalları ən çox 10 simvol uzunluğundadır. Başlanğıc dəyişən S verilmiş ilk qaydanın başlığıdır.
Qaydalardan sonra axtarılacaq ən çox 100 sətir mətn gəlir, hər biri ən çox 50 simvol uzunluğundadır. Giriş yalnız İngilis kiçik hərfləri və boşluqlardan ibarətdir. Giriş faylın sonunda bitir.
Çıxış verilənləri
Axtarılacaq hər sətir üçün qrammatikanın yarada biləcəyi ən uzun boş olmayan alt sətiri çap edin. Əgər ən uzun üçün bərabərlik varsa, sətirdə daha erkən görünən alt sətiri verin. Əgər uyğun alt sətir yoxdursa, böyük hərflərlə NONE çap edin.