KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up


Problem S. 69. (February 2012)

S. 69. Given a text of N characters, we would like to find K patterns, each of length M characters. Unfortunately, letters of the patterns to be recognized are scrambled, consequently, you have to find any permutations of the given patterns in the text.

The text is read from the standard input. The first line of the input contains 3 integers, separated by a space: the values of N, M and K (1\le N\le
1\;000\;000, 1\leM\le1000, 1\le K\le 10\;000). The second line of the input contains the text of length N, finally, the next K lines contain the K patterns of length M. Characters are chosen only from the 26 lower case letters of the English alphabet.

The solution -- written to the standard output -- should contain K lines. The ith line should contain either the least position from which one can find an arbitrary permutation of the ith pattern in the text of length N, or the number ,,0'', if there is no such position.

In the example, ,,Példa bemenet'' is the sample input, while ,,Példa kimenet'' is the corresponding output.

The source code of your program (s69.pas, s689.cpp, ...) -- without the .exe or any other auxiliary files generated by the compiler -- should be submitted in a compressed file s69.zip, also containing a brief description of your solution (s69.txt, s69.pdf, ...) and the name of the developer environment to use for compiling.

(10 pont)

Deadline expired on 12 March 2012.


15 students sent a solution.
10 points:Adrián Patrik, Havasi 0 Márton, Marussy Kristóf, Nagy Róbert, Szabó 928 Attila, Szilágyi Dániel.
9 points:Jákli Aida Karolina, Kucsma Levente István.
8 points:2 students.
7 points:3 students.
5 points:1 student.
3 points:1 student.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley