Análisis de estructuras de sufijos de strings

Abstract

El problema de desarrollar algoritmos que decidan si un cierto patrón o palabra aparece o no en un determinado texto es fundamental en ciencias de la computación. Diversos algoritmos se han desarrollado en las últimas décadas para resolver este problema (y sus múltiples variantes). Un análisis detallado de las complejidades temporales y espaciales de dichos algoritmos revela que, en la práctica, algoritmos de fuerza bruta no son viables en la mayoría de los casos. En este trabajo, se presentaron, de manera formal y estructurada, dos estructuras ampliamente utilizadas en diversos trabajos. Además, utilizando las mismas, se presentaron soluciones a tres de los principales problemas en el área de estudio.

The problem of developing algorithms that can decide whether a certain pattern or word occurs in a certain text is really important in Computer Science. Several algorithms have been created in the last decades to solve this problem (and its variants). A detailed analysis of computational and spatial complexity of these algorithms shows that, in many cases, brute force solutions are not good enough. During this work we introduced, in a formal and structured way, two data structures that are widely used in several works. Also, by using them, we presented solutions to three of the main problems in the field of study.