Queries y LCPs


Submit solution

Points: 100 (partial)
Time limit: 2.5s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Alex tiene un arreglo de n strings, él quiere hacer m operaciones:

  • determinar el LCP desde la posición i a la posición j inclusive,
  • cambiar todos los strings de i a j inclusive, por el string w.

Como Alex es un pequeño programador no sabe como resolver esto en tiempo. Ayúdalo.

Ten en cuenta que el LCP (Longest Common Prefix) de un conjunto de strings, es el mayor prefijo común de estos.

Entrada

La primera línea contiene los enteros n y m \; (1 \leq n, m \leq 10^5).

La segunda línea contiene el arreglo de n strings. Cada string está separado del anterior por un espacio.

Las siguientes m líneas tienen uno los siguientes formatos:

  • 1 \; i \; j (determinar LCP de i a j inclusive)
  • 2 \; i \; j \; w (cambiar strings de i a j inclusive por string w)

Para i, j tal que (1 \leq i \leq j \leq n).

Todas los strings de la entrada están formados por letras minúsculas del alfabeto inglés. El tamaño de cada string no excede los 10 caracteres.

Salida

Para cada operación de tipo 1 imprima el LCP en el rango requerido. Imprima una respuesta por línea.

Ejemplo de entrada

7 3
rhm rh rh rhm r rh r
1 2 3
2 1 6 rhm
1 2 7

Ejemplo de salida

2
1

Comments


  • 0
    Sekai02  commented on Oct. 28, 2020, 9:41 p.m. edit 2

    Think a little bit more :)


    • 0
      Primervirgen  commented on Oct. 28, 2020, 11:07 p.m.

      Por gente como tú, el mundo prospera xD


      • 0
        Sekai02  commented on Oct. 29, 2020, 12:24 a.m.

        lol


  • -4
    Primervirgen  commented on Oct. 28, 2020, 8:41 p.m. edited

    ...