Búsqueda casi óptima de subrepeticiones maximales en una palabra
Autores: Kolpakov, Roman
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Búsqueda casi óptima de subrepeticiones maximales en una palabra
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Corregido
Subrepetición
Factor
Exponente
Maximal
Algoritmo
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 21
Citaciones: Sin citaciones
Para algún fijo tal que , una -subrepetición en una palabra es un factor cuyo exponente es menor que 2 pero no es menor que (el exponente del factor es la relación entre la longitud del factor y su período mínimo). La -subrepetición es máxima si no se puede extender hacia la izquierda o hacia la derecha por al menos una letra mientras se conserva su período mínimo. En el artículo, proponemos un algoritmo para buscar todas las -subrepeticiones máximas en una palabra de longitud en tiempo (el límite inferior para este tiempo es ). Mejora los límites de complejidad temporal conocidos previamente para resolver este problema.
Descripción
Para algún fijo tal que , una -subrepetición en una palabra es un factor cuyo exponente es menor que 2 pero no es menor que (el exponente del factor es la relación entre la longitud del factor y su período mínimo). La -subrepetición es máxima si no se puede extender hacia la izquierda o hacia la derecha por al menos una letra mientras se conserva su período mínimo. En el artículo, proponemos un algoritmo para buscar todas las -subrepeticiones máximas en una palabra de longitud en tiempo (el límite inferior para este tiempo es ). Mejora los límites de complejidad temporal conocidos previamente para resolver este problema.