A este tipo de algoritmos también se les llama Algoritmos de patrones en un texto, algoritmos de emparejamiento de secuencias, algoritmos de casamiento de secuencias o simplemente por su nombre en inglés string matching. Este tipo de algoritmos persiguen encontrar subcadena/s con alguna propiedad en una cadena de caracteres.
Normalmente se denomina patrón/es a la/ subcadena/s buscada/s y texto a la cadena en la que se realiza la búsqueda. Se suelen emplear las letras m y n para referirnos a la longitud de un patrón y a la longitud del texto respectivamente. Podemos asumir que n>m
Este tipo de algoritmos se pueden clasificar según el número de subcadenas que se intentan buscar en simples, se busca sólo una subcadena, y múltiples, se buscan varias subcadenas.
También llamados por su denominación en inglés Single string Matching. En este tipo de algoritmos sólo se busca una subcadena a la que llamamos patrón, es decir el objetivo es encontrar todas las ocurrencias del patrón p dentro del texto. Este tipo de algoritmos se suelen agrupar en alguno de los siguientes tipos
También llamados por su denominación en inglés Multiple String Matching. Ahora no tenemos un solo patrón p a buscar sino que contamos con un conjunto P={p1,..., pl} de patrones. La solución que se suele adoptar es la extensión de los esquemas anteriores para el caso múltiple. Por tanto tenemos los siguientes subtipos:
Escribe un comentario o lo que quieras sobre Algoritmos de búsqueda de subcadenas (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)