Polish version    English version  
  Olympic camps


 News
 About Olympic
 History of OI
 OI books
 National team
 Olympic camps
III camp 2002
IV camp 2003
V camp 2005
VI camp 2005
 Photo gallery
 Links
 SIO
 MAIN
This document is not available in English version.

III Obóz im. A. Kreczmara 2002

Zadanie: d
Autor: Piotr Sankowski
D: Literowe permutacje tekstów

dzień czwarty 9 sierpnia 2002
Plik źródłowy: d.??? (np. pas, c, cpp)
Plik wejściowy: d.in
Plik wyjściowy: d.out

Permutacja liter to przypisanie literom liter w taki sposób, aby każdej literze była przypisana inna litera. Literową permutacją tekstu nazywamy tekst powstały poprzez zamianę liter w wejściowym tekście zgodnie z pewną permutacją liter. Twoim zadaniem jest znalezienie liczby wystąpień literowych permutacji zadanego wzorca w zadanym tekście. Permutacje liter zawierają wszystkie małe litery alfabetu angielskiego.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego d.in tekst i wzorzec,
  • policzy, ile razy permutacje literowe wzorca występują w tekście,
  • zapisze do pliku wynikowego d.out liczbę wystąpień permutacji literowych wzorca w tekście.

Wejście

W pierwszym wierszu pliku tekstowego d.in znajdują się dwie liczby całkowite n i m oddzielone spacją (1 <= n <= 1000000; 1 <= m <= 1000), oznaczające odpowiednio długość tekstu i długość wzorca. W kolejnym wierszu zapisanych jest n małych angielskich liter nieoddzielonych spacjami. Jest to tekst. W następnym wierszu zapisanych jest m małych angielskich liter nieoddzielonych spacjami. Jest to wzorzec.

Wyjście

Plik tekstowy d.out powinien zawierać jedną liczbę całkowitą będącą liczbą wystąpień permutacji literowych wzorca w tekście.

Przykład

Dla pliku wejściowego d.in:

8 4
aabbaabb
aabb

poprawną odpowiedzią jest plik wyjściowy d.out:

3



Print friendly version