Contando prefijos palíndromos

Submit solution
Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
ymondelo
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Dado un conjunto de cadenas compuestas por letras mayúsculas del alfabeto inglés, usted debe calcular por cada unas de ellas la cantidad de prefijos palíndromos que contienen al menos una vocal. Una cadena palíndromo es aquella que se puede leer de la misma forma de izquierda a derecha y de derecha a izquierda. Un prefijo no es más que una subcadena que comienza desde el primer caracter de la cadena original.

Entrada

La primera línea de entrada contiene un número entero 1 \leq N \leq 25. Las siguientes N líneas contienen una cadena de letras mayúsculas del alfabeto inglés ('A' hasta 'Z') de a lo sumo 100\,000 caracteres de longitud.

Salida

Usted debe imprimir una línea por cada caso de la entrada, conteniendo un número entero que representa la cantidad de prefijos palíndromos que contienen al menos una vocal en la palabra correspondiente a cada caso.

Ejemplo de Entrada

5
ABA
ABABB
BBABABB
BABAA
BAB

Ejemplo de Salida

2
2
1
1
1

Especificaciones sobre casos de prueba

  • 3 casos de prueba con valor de 5 puntos cada uno, en los cuales las cadenas tienen a lo sumo 100
  • 3 casos de prueba con valor de 10 puntos cada uno, en los cuales las cadenas tienen a lo sumo 1000 caracteres.
  • 1 casos de prueba con valor de 15 puntos, en el cual las cadenas tienen a lo sumo 5000 caracteres.
  • 1 casos de prueba con valor de 20 puntos, en el cual las cadenas tienen a lo sumo 50000 caracteres.
  • 1 casos de prueba con valor de 20 puntos, en el cual las cadenas tienen a lo sumo 100000 caracteres.

En algunos casos de prueba, las cadenas tienen solo letras entre 'A' y 'E' (i.e. 'A', 'B', 'C', 'D' y 'E').

Comments


  • 0
    linkyless  commented on May 26, 2022, 4:08 a.m.

    Este problema debería ser Tipo "String" en todo su esplendor.


  • 0
    Primervirgen  commented on Jan. 28, 2020, 4:29 p.m.

    Ya lo resolvi con una pequeña optimizacion, gracias


  • 4
    aniervs  commented on Jan. 28, 2020, 3:45 p.m.

    Deberían cambiar la clasificación del problema a String.


  • 0
    Primervirgen  commented on Jan. 28, 2020, 2:52 p.m.

    Necesito ayuda, el ultimo Caso de Prueba de da TLE. Compruebo si el prefijo es palindromo mediante Hashing y luego con una Fuerza Bruta ,miro si existe al menos una vocal en la subcadena original, me pudieran decir como optimizar el tiempo.....


    • 0
      aniervs  commented on Jan. 28, 2020, 3:28 p.m. ← edited

      Para lo de la vocal puedes hacer una tabla acumulativa, específicamente: S[j] la cantidad de vocales 1...j. Entonces la cantidad de vocales en el rango [i,j] es S[j]-S[i-1]. De hecho se puede hacer más fácil ya que si un prefijo 1...i tiene una vocal entonces cualquier prefijo 1...j (con j\ge i) tiene una vocal.


  • 1
    Primervirgen  commented on Aug. 31, 2019, 6:41 a.m.

    Puedo usar Hashing para resolver este problema?


    • 0
      Leonardo  commented on Sept. 1, 2019, 12:16 a.m.

      Si se puede hacer con hashing


  • 0
    cdamianlv  commented on March 1, 2018, 5:40 p.m.

    si no se usar ese algoritmo


  • 0
    yuniels  commented on Feb. 24, 2018, 8:08 p.m.

    como utilizas hash


  • 0
    dcq  commented on Feb. 21, 2018, 12:23 p.m.

    no conozco ese algoritmo si me pudieras decir el metodo?


  • -2
    dcq  commented on Feb. 20, 2018, 3:13 a.m.

    como puedo reducir el tiempo?


  • -1
    dcq  commented on Feb. 19, 2018, 8:44 p.m.

    como puedo reducir el tiempo de este problema?


    • 0
      KhozmoS  commented on Feb. 20, 2018, 7:27 p.m.

      @dcq si te refieres a hacer un algoritmo mas efieciente yo utilice hash para comprobar si eran palindromos.