SKI

02.11.2010

ASK - punktacja

Każdy test (grupa) - 10 punktów.

30.10.2010
TrudnośćTrudnośćTrudność

Wzorzec

Wzorzec

Limit czasowy: 1000 milisekund
Limit pamięciowy: 32000 kilobajtów


Ulubionym zagadnieniem Władka jest problem wyszukiwania wzorca. Przez cały semestr uczęszczania na wykłady z Algorytmów Tekstowych, Władek opracował ponad 10 różnych sposobów rozwiązania tego zadania. Możliwe to było dzięki wykorzystaniu w mniej lub bardziej pokrętny sposób nowo poznanych algorytmów, które nierzadko przeznaczone były do zupełnie innych celów. Niestety, na egzaminie końcowym Władek nie dostał możliwości pochwalenia się nowo nabytą wiedzą - zamiast tego otrzymał następujący problem do rozwiązania: mając dany wzorzec P i tekst T, ile razy dowolnie powiększony P występuje w T?

Wzorzec powiększony k razy, to taki wzorzec w którym każda litera została zastąpiona tą samą literą powtórzoną k razy. Przykładowo, kolejne powiększenia wzorca aabc, to aabc, aaaabbcc, aaaaaabbbccc, aaaaaaaabbbbcccc, itd. Wystąpienie dowolnie powiększonego wzorca P, to takie i, że P powiększony pewną liczbę razy występuje w T począwszy od i-tej litery. Jeżeli więć na pozycji i zaczyna się kilka różnych powiększeń wzorca, to takie wystąpienie liczymy tylko raz (patrz drugi przykład).

Wejście:

W pierwszej linii znajdują się dwie, oddzielone pojedynczym odstępem liczby całkowite n i m (1<=n,m<=1000000). W drugiej linii znajduje się n-elementowy ciąg małych liter alfabetu łacińskiego - jest to tekst T. W trzeciej linii znajduje się m-elementowy ciąg małych liter alfabetu łacińskiego - jest to wzorzec P.

Wyjście:

W pierwszej i jedynej linii Twój program powinien wypisać liczbę wystąpień wzorca w podanym tekście z dowolnym powiększeniem.

Przykład:

Dla danych wejściowych:
6 2
abaabb
ab

poprawną odpowiedzią jest:
3

Wystąpienia wzorca: abaabb, abaabb ,abaabb.

Dla danych wejściowych:
4 1
aaaa
a

poprawną odpowiedzią jest:
4

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
20.10.2010

Start SKI 2010 już 27 października!

Wszystkich młodych programistów zapraszamy do rozpoczęcia kolejnego sezonu zawodów informatycznych konkursem SKI 2010! Do wygrania, oprócz atrakcyjnych nagród rzeczowych, możliwość spróbowania swoich sił w międzynarodowych zawodach drużynowych CERC 2010!

Szczegółowe informacje i regulamin konkursu na stronie http://informatyka.wroc.pl/ski2010

 

 

 

29.10.2009

Zadania z SKI 2009

Chętni mogą się już zmierzyć z zadaniami ze Spontanicznego Konkursu Informatycznego 2009. Zadania są połączone z tymi samymi testami, które były wykorzystane podczas zawodów.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com