Kosmosa pētnieks

Uzdevums

Kosmosa pētnieks Almands jau sen pieraksta no kosmosa nākošos signālus. Katra signāla pierakstīšanai Almands lieto vienu simbolu. Tā kā signāli mēdz atkārtoties, tad vienādo signālu pierakstīšanai vienmēr tiek lietots viens un tas pats simbols, bet dažādu signālu pierakstīšanai tiek lietoti atšķirīgi simboli.

Lai kļūtu slavens kosmosa pētnieku aprindās, Almands cer sagaidīt noteiktu signālu virkni garumā N (N ≥ 1), ko viņš ir nosaucis par paroli. Diemžēl, pēc vairāku gadu desmitu darba (un ļoti garas uztverto signālu virknes pierakstīšanas) Almands ir uzzinājis, ka dažādu signālu izplatīšanās ātrums Visumā var būt dažāds, kas nozīmē to, ka sākumā izsūtīto signālu secība var mainīties. Vēl trakāk - daži signāli to sūtīšanas laikā varēja “sabojāties”, un viena signāla vietā varētu būt uztverts pavisam cits.

Lai tomēr varētu izmantot pierakstīto signālu virkni, Almands ir nolēmis pētīt šīs virknes fragmentus - vienu vai vairākus pēc kārtas sekojošus signālus pierakstītajā signālu virknē. Almands ir izveidojis divas definīcijas:

• Virknes fragmentu garumā N sauc par izcilu, ja, tas vai nu sakrīt ar paroli, vai arī, pārkārtojot tajā signālu kārtību, var iegūt paroli.
• Virknes fragmentu garumā N sauc par labu, ja, pārkārtojot tajā signālus, var iegūt virkni, kurā ar paroli sakrīt vismaz L (1 ≤ L < N) signāli.

Skaidrs, ka katrs izcils fragments vienlaicīgi ir arī labs fragments.

Uzrakstiet programmu, kas dotai parolei, L vērtībai un pierakstīto signālu virknei nosaka, cik dažādās vietās pierakstīto signālu virknē atrodami izcili, un cik vietās - labi fragmenti!

Ievaddati

Teksta faila kosmoss.dat pirmajā rindā doti trīs naturāli skaitļi: N (paroles garums, N  ≤ 10 000), L (mazākais simbolu skaits, kādam jāsakrīt, lai fragments tiktu uzskatīts par labu, 1 ≤ L < N) un M (pierakstītās signālu virknes garums, M ≤ 1 000 000). Katri divi blakusskaitļi ir atdalīti ar tukšumzīmi.

Faila otrajā rindā dots paroles pieraksts - simbolu virkne garumā N.

Faila trešajā rindā dota pierakstīto signālu virkne - simbolu virkne garumā M.

Parole un simbolu virkne var saturēt tikai 80 dažādus simbolus, kas doti tabulā:

Izvaddati

Teksta faila kosmoss.rez vienīgajā rindā jāizvada divi veseli nenegatīvi skaitļi, kas atdalīti ar tukšumzīmi, - dažādo vietu skaits pierakstīto signālu virknē, kur iespējams atrast izcilu fragmentu, un dažādo vietu skaits, kur iespējams atrast labu fragmentu.

Piemērs

kosmoss.dat	kosmoss.rez
5 3 11 abaks abrakadabra	0 7
kosmoss.dat	kosmoss.rez
5 4 11 abaks abrakadabra	0 3
kosmoss.dat	kosmoss.rez
5 4 11 abaks nabagsabaks	2 6

Atsauces