Conteo de subcadenas con inserciones
Autores: Brank, Janez; Hoevar, Toma
Idioma: Inglés
Editor: MDPI
Año: 2025
Acceso abierto
Artículo científico
2025
Conteo de subcadenas con inserciones
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Problema algorítmico clásico
Complejidad temporal lineal
Conteo de subcadenas
Variación
Inserción
Periodicidad de cadenas
Implementación en C++
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 32
Citaciones: Sin citaciones
La búsqueda de subcadenas es un problema algorítmico clásico con numerosas soluciones que logran una complejidad temporal lineal. En este documento, abordamos una variación del problema en el que, dadas tres cadenas , , y , estamos interesados en el número de ocurrencias de en todas las cadenas que resultarían de insertar en en cada posición posible. Básicamente, estamos resolviendo varios problemas de conteo de subcadenas de la misma subcadena en cadenas relacionadas. Presentamos una descripción detallada de varios enfoques conceptualmente diferentes para resolver este problema y concluimos con un algoritmo que tiene una complejidad temporal lineal. La solución se basa en un resultado reciente del campo de la búsqueda de subcadenas en secuencias comprimidas y explota la periodicidad de las cadenas. También proporcionamos una implementación independiente del algoritmo en C++ y verificamos experimentalmente su comportamiento, principalmente para demostrar que su tiempo de ejecución es lineal en las longitudes de las tres cadenas de entrada.
Descripción
La búsqueda de subcadenas es un problema algorítmico clásico con numerosas soluciones que logran una complejidad temporal lineal. En este documento, abordamos una variación del problema en el que, dadas tres cadenas , , y , estamos interesados en el número de ocurrencias de en todas las cadenas que resultarían de insertar en en cada posición posible. Básicamente, estamos resolviendo varios problemas de conteo de subcadenas de la misma subcadena en cadenas relacionadas. Presentamos una descripción detallada de varios enfoques conceptualmente diferentes para resolver este problema y concluimos con un algoritmo que tiene una complejidad temporal lineal. La solución se basa en un resultado reciente del campo de la búsqueda de subcadenas en secuencias comprimidas y explota la periodicidad de las cadenas. También proporcionamos una implementación independiente del algoritmo en C++ y verificamos experimentalmente su comportamiento, principalmente para demostrar que su tiempo de ejecución es lineal en las longitudes de las tres cadenas de entrada.