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.
| Problema | Competencia | Dificultad |
|---|---|---|
| La calculadora del almacén | 2017 Regional | 🟢 fácil |
| El juego del OCIo | 2018 Regional | 🟢 fácil |
| Secuencia de ADN | 2019 Regional | 🟢 fácil |
| El cifrado de César | 2020 Nacional | 🟢 fácil |
| Burrito de letras | 2024 Nacional | 🟢 fácil |
| El flojo de Lucas | 2016 Nacional | 🟡 media |
| Contraseña | 2022 Regional | 🟡 media |
| Reloj inteligente | 2018 Regional | 🟡 media |
| Las sumas de Gabriela | 2018 Regional | 🟡 media |
| La biblioteca perdida de la cultura Chipotle | 2018 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.
| Problema | Año | Media (puntos parciales) | Lograron 100 |
|---|---|---|---|
| Mutating DNA | 2021 | 93/100 | 86% |
| Hieroglyphs | 2024 | 5/100 | <1% |