Suffiks pulemyotu
_Ya zaçot, ya da avtomat.___________________
Hannibal Rektor
Possiltum ordusunun yeni əsgərlərinin nəzəri hazırlanmasına yalnız hərbi hüquqlar deyil, həmçinin kriptoqrafiyanın əsasları da daxil idi. Mühazirələri əsgər zarafatına biganə olmayan mayor Meqa Bayt oxuyurdu. Qarşılarına Possiltum ordusunu içəridən dağıtmaq tapşırığı qoyulmuş Qvido və Nunçio terminalogiyaya dolaşıqlıq əlavə edərək bununla oynamaq qərarına gəldilər. Növbəti mühazirədə Nunçio əlini qaldırdı və soruşdu:
- Bax siz keçən mühazirədə sonlu avtomatlar haqqında danışdınız. Bəs sonlu pulemyot haqqında danışacaqsınız?
Meqa Bayt özünü itirmədi.
- Suffiks pulemyotu – bu verilmiş sətrin (sıfırdan L-ə qədər, L də daxil olmaqla, burada L sətrin uzunluğudur) bütün suffikslərini qəbul edən sonlu avtomatdır. Serjant Qvido!
- Mən, cənab mayur!
- Siz avtomatı pulemyotdan ayıra bilərsiz?
- Əlbətdə, cənab mayor!
- Sizə sonlu avtomat verilib. Onun verilmiş sətrin suffiks pulemyotu olduğunu yoxlamaq tələb olunur.
Təəssüf ki, belə bir proqramın yazılması Sindikatda, həmçinin M.İ.F şirkətində olduğu kimi Qvido və Nunçionun vəzifələrinə daxil deyildir. Buna görə də uyğun proqramı Sizin yazmağınız lazım gələcəkdir.
Giriş verilənləri
Giriş faylında bir neçə test dəsti verilir. Hər bir dəstin birinci sətrində avtomatın vəziyyətlərinin N sayı, M keçidlərinin sayı, həmçinin T vəziyyətlərinin qəbul edilməsi sayı verilir (1 ≤ T ≤ N ≤ 50000, 1 ≤ M ≤ 100000). İkinci sətirdə avtomatın vəziyyətlərini artan ardıcıllıqla alan 1-dən N-qədər hüdudunda boşluqla ayrılmış T sayda müxtəlif ədəd verilir. Növbəti M sətirlərdə keçidlər a_i b_i c_i şəklində verilir, burada 1 ≤ a_i, b_i ≤n, c_i isə latın əlifbasının kiçik hərfidir. a_i vəziyyətindən b_i vəziyyətinə keçid c_i hərfinə görə aparılır. Hər bir a_i vəziyyətindən c_i simvoluna görə birdən çox olmayan keçid vardır. Dəstin sonuncu sətrinin təsviri – avtomatın pulemyot olması lazım gələn S sətridir. O yalnız kiçik latın hərflərini ehtiva edir, onun uzunluğu 1-dən 50000-ə qədər ola bilər. Bundan başqa bütün N-lərin cəmi və yoxlanılması lazım gələn bütün sətirlərin uzunluqları cəmi 50000-ni, bütün M-lərin cəmi isə 100000-ni aşmır.
Fayl N=M=T=0 qondarma dəstlə tamamlanır.
Avtomatın ilkin vəziyyəti birincidir. Əgər hansısa sətrin şərhi zamanı avtomatda uyğun keçid olmazsa, onda avtomat səhvdən dolayı boşalır və sətri qəbul etmir. Bu şəkildə sətir, əkər onun şərhi zamanı bütün keçidlər tapılmış olarsa. Qəbul edilir və onlar bitdikdən sonra avtomat qəbuledici vəziyyətində olur (bu zaman yolda qəbuledici vəziyyətinin olub olmaması əhəmiyyət kəsb etmir).
Çıxış verilənləri
Nümunədəki formata uyğun verilmiş avtomatın pulemyot olub olmadığını çıxış faylına verin.