Algunos pensamientos y una respuesta parcial a mí mismo:
peor de los casos para el algoritmo de fuerza bruta:
a^(n+1) b en (a^n b)^m
por ejemplo, aaab en aabaabaabaabaabaabaab
peor caso para SMOA:
Algo así como yxyxyxxyxyxyxx en (yxyxyxxyxyxyxy)^n. Necesita mayor refinamiento. Estoy tratando de asegurar que cada avance sea solo la mitad de la duración de la coincidencia parcial, y que el cálculo del sufijo máximo requiera la máxima cantidad de retroceso. Estoy bastante seguro de que estoy en el camino correcto porque este tipo de caso es la única forma que he encontrado hasta ahora para hacer que mi implementación de SMOA (que es asintóticamente 6n+5) funcione más despacio que glibc's Two-Way (que es asintóticamente) 2n-m pero tiene una sobrecarga de preprocesamiento moderadamente dolorosa).
peor de los casos para cualquier cosa rodadura-hash basado:
Cualquiera que sea la secuencia de bytes provoca colisiones hash con el hash de la aguja. Para cualquier hash razonablemente rápido y una aguja dada, debería ser fácil construir un pajar cuyo hash colisiona con el hash de la aguja en cada punto. Sin embargo, parece difícil crear simultáneamente coincidencias parciales largas, que son la única forma de obtener el peor de los casos. Naturalmente, para el peor de los casos, la aguja debe tener cierta periodicidad y una forma de emular el hash ajustando solo los caracteres finales.
peor de los casos de dos vías:
parece ser muy corto aguja con la descomposición de MS no trivial - algo así como bac - donde el pajar contiene repetidas falsos positivos en el componente de la mitad derecha de la aguja - algo así como dacdacdacdacdacdacdac . La única forma en que este algoritmo puede ser lento (aparte de que los autores de glibc lo implementan de forma deficiente ...) es haciendo que el bucle externo itere muchas veces e incurra repetidamente en esa sobrecarga (y haciendo que la sobrecarga de configuración sea significativa).
Otros algoritmos:
estoy muy interesado sólo en algoritmos que son O(1) en el espacio y tienen una baja sobrecarga de procesamiento previo, por lo que no han mirado sus peores casos tanto. Al menos Boyer-Moore (sin las modificaciones para que sea O(n)) tiene un peor caso no trivial donde se convierte en O(nm).
¿Cuál es su objetivo final aquí? ¿Solo para aprender sobre los algoritmos? ¿O tienes una aplicación con agujas/pajares inusuales? – Cascabel
En el corto plazo, solo para aprender sobre los algoritmos. A largo plazo, tengo una implementación de biblioteca C orientada hacia un tamaño muy pequeño con un rendimiento superior al promedio que usa el enfoque ingenuo de strstr, y me gustaría considerar reemplazarlo con uno de los O (n) tiempo/O (1) algoritmos espaciales. SMOA parece prometedor, pero quiero ver si el constante 6 en el límite superior 6n + 5 en las comparaciones es problemático en la práctica (mis pruebas iniciales muestran que es mucho más bajo en datos de manera remota y comparable en rendimiento a glibc sin todas las especialidades). carcasa para agujas cortas/largas). –