Strings y Secuencias

Trie, procesamiento básico, subsecuencias (LIS/LCS).

Volver a los 11 temas · Referencia · temarios: Syllabus OCI · Syllabus IOI.

📍 Clases relacionadas: módulos 00 · 22 de la Ruta de Aprendizaje.

📋 En el temario OCI: desde la Regional (♡): lectura y manipulación básica de strings.

Trabajar con texto y con secuencias: buscar, comparar, contar. Ojo con la expectativa: en la IOI el peso está en las secuencias (LIS, LCS) mucho más que en los algoritmos famosos de strings.

📌 Qué abarca

  • Procesamiento básico de strings y búsqueda ingenua de substring.
  • Trie (árbol de prefijos).
  • Técnicas de secuencias que en realidad son DP/EEDD (LIS, LCS, subsecuencias) → ver Programación Dinámica.

⛔ Fuera del syllabus IOI (¡atención!)

  • Hashing (Rabin-Karp), KMP, Z-function.
  • Suffix array / tree, suffix automaton, Aho-Corasick.

Toda la maquinaria de strings avanzada está excluida: ningún problema la requiere.

🎯 En competencia

En la OCI — Desde la Regional, pero solo manipulación básica: recorrer un string, contar caracteres, comparar, invertir. Los algoritmos de strings (hashing, KMP, tries) no entran en ninguna fase. En este vault hay 10 problemas OCI del tema (6 de fases regionales y 4 de fases nacionales); están en la tabla de abajo.

En la IOI — Salvo tries y manipulación básica, no esperes problemas que dependan de algoritmos de strings. Si un problema usa cadenas, casi siempre es ad-hoc.

⚠️ La trampa típica

Construir texto con s = s + t dentro de un ciclo: cada paso copia todo lo anterior y un proceso lineal se vuelve O(n²). Usa s += t.

🧱 Estructuras de datos

Se implementan a mano — hay que saber construirlas:

Todas juntas y comparables en el Catálogo de estructuras.

🇨🇱 Problemas OCI (en español)

Empieza por acá: son problemas oficiales chilenos, con enunciado en español y mirror para enviar. Consulta la orientación de estudio al comienzo de esta página. La dificultad orienta la elección, pero no garantiza una solución completa.

ProblemaCompetenciaDificultad
La calculadora del almacén2017 Regional🟢 fácil
El juego del OCIo2018 Regional🟢 fácil
Secuencia de ADN2019 Regional🟢 fácil
El cifrado de César2020 Nacional🟢 fácil
Burrito de letras2024 Nacional🟢 fácil
El flojo de Lucas2016 Nacional🟡 media
Contraseña2022 Regional🟡 media
Reloj inteligente2018 Regional🟡 media
Las sumas de Gabriela2018 Regional🟡 media
La biblioteca perdida de la cultura Chipotle2018 Nacional🔴 difícil

🌍 Problemas IOI

De más abordable a más duro, según el puntaje promedio que sacaron los competidores: una media alta sugiere más puntos parciales accesibles, no más soluciones completas. Consulta también el porcentaje de 100 y los prerrequisitos.

ProblemaAñoMedia (puntos parciales)Lograron 100
Mutating DNA202193/10086%
Hieroglyphs20245/100<1%