Psevdotomat#4608
Verilmiş S ardıcıllığı üçün, bu ardıcıllığın bütün sonluqlarını (və ola bilsin digər sonlu sətirləri) qəbul edən deterministik sonlu avtomat qurun. Avtomat mümkün olan ən az sayda vəziyyətdən ibarət olmalıdır. Avtomatın hər bir vəziyyəti son vəziyyət kimi qəbul edilir. Başlanğıc vəziyyətin nömrəsi 1-dir.
Aşağıda "abacaba" ardıcıllığı üçün test nümunəsindən avtomat göstərilmişdir.
Tək bir sətirdə kiçik latın hərflərindən ibarət olan S sözü verilir.
Birinci sətirdə iki ədəd N və K — vəziyyətlərin və keçidlərin sayı. Sonra K sətir, hər birində iki ədəd a_i, b_i və hərf c_i, bu keçidin a_i vəziyyətindən b_i vəziyyətinə c_i hərfi ilə olduğunu göstərir. Keçidləri istənilən ardıcıllıqla təqdim edə bilərsiniz. Əgər bir neçə həll varsa, istənilən birini təqdim edə bilərsiniz.
Məhdudiyyətlər
1 ≤ |S| ≤ 5000
1 ≤ a_i, b_i ≤ N
'a' ≤ c_i ≤ 'z'
Nümunə 1