Birləşdirilmiş Sətirlərin Axtarışı
World Wide Web-dəki məlumatların miqdarı sürətlə artır. Bu informasiya partlayışı dövründə yalnız ehtiyaclarımıza uyğun məlumatları ehtiva edən veb səhifələrə daxil olmaqla sağ qalmalıyıq. Bu məqsədlə əsas texnologiyalardan biri açar söz axtarışıdır. Tanınmış axtarış sistemlərindən istifadə edərək, maraqlandığımız mövzu haqqında faydalı məlumatları ehtiva edən səhifələrə asanlıqla daxil ola bilərik.
Açar söz axtarışı problemlərinin bir çox variasiyası mövcuddur. Əgər verilmiş mətn daxilində tək bir sıra axtarılırsa, problem olduqca asandır. Əgər axtarılacaq nümunə bir neçə sıradan ibarətdirsə və ya müntəzəm ifadələr kimi güclü bir notasiya ilə verilirsə, bu tapşırığı səmərəli şəkildə yerinə yetirmək üçün mürəkkəb alqoritmlər tələb olunur.
Bizim problemimizdə bir sıra (element sıraları) verilir, lakin onlar birbaşa axtarılmır. Bütün element sıralarının istənilən ardıcıllıqla birləşmələri burada axtarışın hədəfləridir.
Məsələn, üç element sırası aa, b və ccc verildiyini düşünün. Bu halda, aşağıdakı altı birləşdirilmiş sıra axtarışın hədəfləridir, yəni mətn daxilində axtarılmalıdır.
aabccc
aacccb
baaccc
bcccaa
cccaab
cccbaa
Mətn bu sıraların bir neçə dəfə təkrarlanmasını ehtiva edə bilər. Sizdən bu sıraların təkrarlanma sayını, daha dəqiq desək, mətn daxilində təkrarlanma mövqelərinin sayını saymağınız xahiş olunur.
İki və ya daha çox birləşdirilmiş sıra eyni ola bilər. Belə hallarda, yuxarıdakı problem bəyanatının incə aspektlərini nəzərə almaq lazımdır. Məsələn, əgər iki element sırası x və xxdirsə, xxx sırası həm x və xx birləşməsinin, həm də xx və x birləşməsinin təkrarlanmasıdır. Təkrarlanma mövqelərinin sayı sayılmalı olduğuna görə, bu hal bir dəfə sayılır, iki dəfə deyil.
İki təkrarlanma üst-üstə düşə bilər. Məsələn, xxxx sırası iki fərqli mövqedə xxx birləşməsinin təkrarlanmasını ehtiva edir. Bu hal iki dəfə sayılır.
Giriş verilənləri
Giriş bir sıra element sıraları və bir mətn verən bir neçə datasetdən ibarətdir. Datasetin formatı aşağıdakı kimidir.
n m
e_1
e_2
...
e_n
t_1
t_2
...
t_m
Birinci sətir boşluqla ayrılmış iki tam ədədi ehtiva edir. n element sıralarının sayıdır. m mətnin təmsil olunması üçün istifadə olunan sətirlərin sayıdır. n 1 ilə 12 arasında, daxil olmaqla, dəyişir.
Sonrakı n sətirin hər biri bir element sırasını verir. Bir element sırasının uzunluğu (simvolların sayı) 1 ilə 20 arasında, daxil olmaqla, dəyişir.
Son m sətir bütövlükdə mətni verir. Çox uzun bir sətirə malik olmaq arzuolunmaz olduğundan, mətn yeni sətirlərlə m sətirə ayrılır, lakin bu yeni sətirlər nəzərə alınmamalıdır. Onlar mətnin hissəsi deyillər. Bu sətirlərin hər birinin uzunluğu (yeni sətir daxil deyil) 1 ilə 100 arasında, daxil olmaqla, dəyişir. Mətnin uzunluğu 1 ilə 5000 arasında, daxil olmaqla, dəyişir.
Element sıraları və mətn kiçik hərflərdən başqa simvollar ehtiva etmir.
Girişin sonu boşluqla ayrılmış iki sıfır ehtiva edən bir sətirlə göstərilir.
DİQQƏT! Nümunə giriş yalnız kiçik datasetləri ehtiva etsə də, qeyd edin ki, 12! × 5000 2^31 -dən çox böyükdür.
Çıxış verilənləri
Girişdəki hər dataset üçün uyğun mövqelərin sayını ehtiva edən bir sətir çıxış edilməlidir. Çıxış sətiri əlavə simvollar ehtiva etməməlidir.