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
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
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.
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.