Magic four
Little-Z has a long string of characters, containing only lowercase english letters. In addition, he has a lot of smaller 4 character strings.
Write him a program, which will for each 4 character string check it's first occurence in main (long) string.
InputIn first line, there will be the main string, 5 <= len(STR) <= 10 000. In second line, there will be a number 5 <= N <= 500 000, followed by N lines, each containing a 4 character word.
OutputOutput N lines, each containing number, representing the position of substring in main string (first place is numbered 1). If such position doesn't exist output 0.
Input:
Output:
abracadabra
5
abra
cada
acab
raca
tacaOutput:
1
5
0
3
0Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.