3334 - Dr. B - Tree I

Created by Luis Manuel Díaz Barón
Added by luismo (2015-06-21)
Limits
Total Time: 15000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Dr. Frank B-Tree is working with texts. He has a string S of length N, and a pattern P of length L. He wants to know how many characters he needs to remove from S so that the remaining string S' consists of pattern P concatenated as many times as possible, but at least once.
Dr. Frank B-Tree está trabajando con textos. Él tiene una cadena S de longitud N, y un patrón P de longitud L. Quiere saber cuántos caracteres tiene que quitar de S para que la cadena restante S' quede compuesta por el patrón P concatenado tantas veces como sea posible, pero al menos una vez.
Dr. Frank B-Tree is working with texts. He has a string S of length N, and a pattern P of length L. He wants to know how many characters he needs to remove from S so that the remaining string S' consists of pattern P concatenated as many times as possible, but at least once.

Input specification

The first line of input contain an integer number N (1 <= N <= 10^5). The second line of input contains a string of exactly N characters denoting the string S. The third line of input contain an integer number L (1 <= L <= N). The fourth and last line of input contains a string of exactly L character denoting the pattern P. Given string contains only capital letters of the English alphabet.
La primera línea de la entrada contiene un número entero N (1 <= N <= 10^5). La segunda línea de la entrada contiene una cadena de exactamente N caracteres que representa la cadena S. La tercera línea de la entrada contiene un número entero L (1 <= L <= N). La cuarta y última línea de entrada contiene una cadena de exactamente L caracteres que representa el patrón P. Las cadenas proporcionadas contienen únicamente letras mayúsculas del alfabeto Inglés.
The first line of input contain an integer number N (1 <= N <= 10^5). The second line of input contains a string of exactly N characters denoting the string S. The third line of input contain an integer number L (1 <= L <= N). The fourth and last line of input contains a string of exactly L character denoting the pattern P. Given string contains only capital letters of the English alphabet.

Output specification

Output an integer denoting the number of characters to be removed. If S' does not contain pattern P at least once, you should output -1.
Usted debe imprimir un entero que indica el número de caracteres a ser eliminados. Si S' no contiene el patrón P al menos una vez, usted debe imprimir de salida -1.
The first line of input contain an integer number N (1 <= N <= 10^5). The second line of input contains a string of exactly N characters denoting the string S. The third line of input contain an integer number L (1 <= L <= N). The fourth and last line of input contains a string of exactly L character denoting the pattern P. Given string contains only capital letters of the English alphabet.

Sample input

13
AXARPARPAARPA
4
ARPA

Sample output

5

Hint(s)