logo móvil
Contáctanos

Conteo de subcadenas con inserciones

Autores: Brank, Janez; Hoevar, Toma

Idioma: Inglés

Editor: MDPI

Año: 2025

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro