Copiado al portapapeles
Descripción
Un clasico problema en procesamiento de cadenas es el siguiente, te dan un texto $t$ y un patron $p$, debes encontrar cuantas y en cuales posiciones aparece dicho patron en el texto.
Ejemplo: $t = "ABABABABA"$ y el patron, $p = "ABA"$ , entonces el resultado es: $4$ ya que aparece $4$ veces en el texto y aparece en las posiciones $[0, 2, 4, 6]$, este es un problema sencillo, asi que se te da algo mas interesante, dado $K$ patrones se debe buscar en el texto, contar cuantos y en que posiciones aparecen, dado que puede haber patrones repetidos y varias respuestas, la salida debe ordenar de acuerdo al siguiente criterio
- Mostrar primero los patrones que aparezcan mas veces en el texto
- Si hay varios con el mismo valor, ordenar por los patrones lexicograficamente (de menor a mayor)
Entrada
La entrada consiste de varias lineas.
La primera linea tiene al texto $t$, ($ 1 \leq |t| \leq 10^2$).
La segunda linea tiene un número entero $k$, ($ 1 \leq k \leq 10^2$), la cantidad de patrones.
Luego vienen $k$ lineas la i-ésima linea tiene una cadena $p$ ($ 1 \leq |p| \leq 10^2$), los patrones a buscar en el texto.
Se garantiza que las cadenas seran letras mayusculas del alfabeto ingles y ademas no tendran espacios.
Salida
La salida tiene $ 2 \cdot k$ lineas.
las siguientes $2 \cdot k$ lineas tiene la siguiente información
El patron y la cantidad de veces que aparece en el texto separados por un espacio.
Luego viene todas las posiciones donde aparece dicho patron.
Ejemplo Entrada
ABABABAB 3 B A AB
Ejemplo Salida
A 4 0 2 4 6 AB 4 0 2 4 6 B 4 1 3 5 7
Ayuda
Ejemplo de entrada
LXF
4
WE
U
EA
SQ
Ejemplo de Salida
EA 0
SQ 0
U 0
WE 0