Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

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, 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 March 12, 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.

Problems in Information Technology of KöMaL, February 2012