logo móvil
Contáctanos

Búsqueda casi óptima de subrepeticiones maximales en una palabra

Autores: Kolpakov, Roman

Idioma: Inglés

Editor: MDPI

Año: 2022

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro