logo móvil
Contáctanos

Más tiempo-espacio intercambios para encontrar una subcadena única más corta

Autores: Bannai, Hideo; Gagie, Travis; Hoppenworth, Gary; Puglisi, Simon J.; Russo, Luís M. S.

Idioma: Inglés

Editor: MDPI

Año: 2020

Descargar PDF

Acceso abierto

Artículo científico
2020

Más tiempo-espacio intercambios para encontrar una subcadena única más corta


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Algoritmo
Encontrar
Subcadenas
Espacio
Tiempo
Desajuste

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 41

Citaciones: Sin citaciones


Descripción
Extendemos resultados recientes sobre encontrar las subcadenas más cortas y únicas (SUSs) para obtener nuevos intercambios tiempo-espacio para este problema y la generalización de encontrar SUSs con -mismatches. Nuestros nuevos resultados incluyen el primer algoritmo para encontrar un -mismatch SUS en espacio sublineal, el cual obtenemos al extender un algoritmo de Senanayaka (2019) y combinarlo con un resultado sobre esbozos de Gawrychowski y Starikovskaya (2019). Primero describimos cómo, dado un texto de longitud y palabras de espacio de trabajo, con alta probabilidad podemos encontrar un SUS de longitud en tiempo usando acceso aleatorio a , o en tiempo usando pasadas secuenciales sobre . Luego describimos cómo, para constante , con alta probabilidad, podemos encontrar un -mismatch SUS en tiempo usando pasadas secuenciales sobre , nuevamente usando solo palabras de espacio de trabajo. Finalmente, también describimos un algoritmo determinístico que toma tiempo para encontrar un SUS usando palabras de espacio de trabajo, donde es un parámetro.

Otros recursos que podrían interesarte

Temas Virtualpro