Definición y solución de una nueva variante de búsquedas de cadenas llamada búsqueda δγ—Parametrizada

Abstract

Esta tesis define un nuevo problema de búsqueda de cadenas que combina dos paradigmas: Búsqueda δγ y Búsqueda Parametrizada. La solución obtenida es una combinación de técnicas de paralelismo de bits y una reducción a un problema the matchings en grafos. La complejidad en tiempo del algoritmo es O(nm), asumiendo que el tamaño del texto es n, el tamaño de patrón es m y que el alfabeto es de tamaño constante. / Abstract. This thesis defines a new pattern matching problem by combining two paradigms: δγ–matching and parameterized matching. The solution is essentially obtained by a combination of bitparallel techniques and a reduction to a graph matching problem. The time complexity of the algorithm is O(nm), assuming text size n, pattern size m and a constant alphabet size.