Find the First Occurrence in a String

Q: ¿Cuál es la complejidad temporal de encontrar la primera aparición de una cadena?

Comprobar cada posición inicial requiere O(n · m) tiempo en el peor caso, donde n y m son las longitudes de la cadena de búsqueda y de la cadena buscada, y O(1) de espacio adicional. El algoritmo de Knuth-Morris-Pratt requiere O(n + m) tiempo y O(m) de espacio para su tabla, independientemente de cuáles sean las letras.

FácilArrays y cadenas Dos punteros

+10

Recibes dos cadenas, haystack y needle. Devuelve el índice de haystack donde comienza la primera aparición de needle, contando desde 0. Si needle nunca aparece en haystack, devuelve -1. Implementa la búsqueda tú mismo en lugar de llamar a una búsqueda de subcadenas integrada, como find o indexOf.

Función

strStr(haystack: string, needle: string) → integer

haystackstring: el texto en el que buscar
needlestring: la cadena que se busca
Devuelveinteger: el índice donde comienza la primera aparición de needle, o -1 si no hay ninguna

Restricciones

1 ≤ haystack.length ≤ 5 × 10⁴
1 ≤ needle.length ≤ 5 × 10⁴
Ambas cadenas contienen únicamente letras minúsculas del inglés.
needle puede ser más largo que haystack. Entonces no puede aparecer, y la respuesta es -1.

Ejemplos

Entrada: haystack = "bananarama"needle = "ana"
Salida: 1
Explicación: Las letras en los índices 1, 2 y 3 forman ana. Una segunda copia comienza en el índice 3 y se superpone a la primera, pero la respuesta es la primera copia, así que es 1.

Entrada: haystack = "pineapple"needle = "apples"
Salida: -1
Explicación: apple comienza en el índice 4, y la cadena de búsqueda termina justo después, así que la s final de la cadena buscada no tiene ninguna letra con la que coincidir. No existe ninguna copia completa de apples, así que la respuesta es -1.

Entrada: haystack = "abcabcabd"needle = "abcabd"
Salida: 3
Explicación: El intento en el índice 0 coincide con cinco letras, abcab, y después encuentra una c donde la aguja espera una d. La copia que funciona empieza en el índice 3 y termina con la d final.

+16 pruebas ocultas al enviar

Para ir más allá

¿Puedes devolver todos los índices donde empieza needle, incluidas las copias superpuestas, y aun así hacerlo en O(n + m)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Comparar needle en cada posición inicial es correcto, pero lento cuando las coincidencias casi tienen éxito: se descarta una coincidencia parcial larga que falla cerca del final, y la siguiente posición inicial vuelve a leer casi las mismas letras. El algoritmo de Knuth-Morris-Pratt conserva ese trabajo. Una tabla construida solo a partir de needle indica qué parte de una coincidencia parcial fallida todavía se puede aprovechar, de modo que el recorrido nunca retrocede en haystack y termina en O(n + m).

Comprueba cada posición inicial

Correcto, pero no termina con las pruebas más grandes

Intuición

Llama n a la longitud de haystack y m a la de needle. Una copia de needle puede empezar en cualquier índice desde 0 hasta n-m. Prueba esos inicios de izquierda a derecha. En cada uno, compara needle con haystack letra por letra y detente en la primera diferencia. El primer inicio en el que coinciden las m letras es la respuesta, y recorrerlos de izquierda a derecha hace que sea la primera copia.

El último inicio es n-m porque una copia que empezara más tarde se pasaría del final de haystack. El mismo límite contempla un needle más largo que haystack: no hay ningún inicio que probar y el bucle llega hasta -1.

El coste se nota cuando coinciden la mayoría de las letras. Toma un haystack de 50,000 as y un needle de 24,999 as seguido de una b. Cada uno de los 25,001 inicios compara 25,000 letras antes de llegar a la b, lo que supone más de 6 × 10^8 comparaciones para obtener una respuesta de -1.

Algoritmo

Sean n y m las longitudes de haystack y needle.
Para cada start desde 0 hasta n-m, establece j en 0.
Mientras j < m y haystack[start + j] sea igual a needle[j], incrementa j.
Si j llegó a m, todas las letras coincidieron: devuelve start.
Si ningún valor de start funciona, devuelve -1.

def strStr(haystack, needle):
    n, m = len(haystack), len(needle)
    for start in range(n - m + 1):
        j = 0
        while j < m and haystack[start + j] == needle[j]:
            j += 1
        if j == m:
            return start
    return -1

Knuth-Morris-Pratt

Intuición

Observa lo que descarta la fuerza bruta. Al buscar abcabd en abcabcabd, el intento en el índice 0 coincide con abcab y luego falla. Esas cinco letras terminan en ab, y ab también es el comienzo de la aguja. Así que, después de la discrepancia, dos letras del siguiente intento útil ya coinciden, y puedes continuar desde el mismo punto del texto.

Un borde de una cadena es un prefijo más corto que también es un sufijo, como ab en abcab. Antes de la búsqueda, crea una tabla lps donde lps[i] es la longitud del borde más largo de needle[0..i]. Para abcabd es [0, 0, 0, 1, 2, 0]. La tabla depende solo de la aguja, y la creas con el mismo bucle de coincidencia, ejecutado sobre la aguja comparándola consigo misma.

Después, recorre el texto una vez y mantén k, el número de letras de la aguja que han coincidido hasta el momento. Si la siguiente letra es igual a needle[k], k aumenta en uno. Si no, asigna lps[k-1] a k y vuelve a comparar la misma letra, hasta que coincida o k sea 0. Retroceder a un borde nunca omite una aparición: cualquier aparición que comience dentro del intento fallido debe empezar con un borde de lo que coincidió, y primero se prueba el borde más largo. Cuando k llega a m, la aparición comenzó en i-m+1.

Por qué esto es lineal: k aumenta como máximo en uno por cada letra del texto, y cada retroceso lo reduce. No puede reducirse más veces de las que aumentó, así que el recorrido toma como máximo 2n pasos, y crear la tabla toma como máximo 2m.

Algoritmo

Construye lps: con k = 0, para cada i desde 1 hasta m-1, retrocede con k = lps[k-1] mientras k > 0 y needle[i] sea distinto de needle[k]; si coinciden, incrementa k; guarda lps[i] = k.
Restablece k a 0 y recorre el texto con el índice i.
Mientras k > 0 y haystack[i] sea distinto de needle[k], establece k = lps[k-1].
Si haystack[i] es igual a needle[k], incrementa k.
Si k es igual a m, devuelve i-m+1. Si el bucle termina, devuelve -1.

def strStr(haystack, needle):
    m = len(needle)
    # lps[i]: length of the longest proper prefix of needle[0..i] that is also its suffix
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and needle[i] != needle[k]:
            k = lps[k - 1]
        if needle[i] == needle[k]:
            k += 1
        lps[i] = k

    k = 0  # how many letters of needle are matched so far
    for i, ch in enumerate(haystack):
        while k > 0 and ch != needle[k]:
            k = lps[k - 1]  # fall back to the longest border, never move i back
        if ch == needle[k]:
            k += 1
        if k == m:
            return i - m + 1
    return -1

Errores comunes y casos límite

La mayoría de los errores se encuentran al final del texto de búsqueda o dentro del bucle de respaldo.

Permitir que el inicio avance hasta n-1 en lugar de n-m. Cuando el final del texto de búsqueda coincide con el inicio del patrón, la comparación lee más allá del final de haystack, lo que hace que Python, Java, Rust y Swift se detengan con un error de índice.
Olvidar que el patrón puede ser más largo que el texto de búsqueda. Con longitudes sin signo, como size_t en C++ o usize en Rust, n-m no puede ser negativo: C++ lo convierte en un número enorme y Rust entra en pánico en una compilación de depuración. Comprueba primero m > n o calcula con enteros con signo.
Escribir el retroceso de KMP con un if en lugar de un while. Al buscar aaa en aabaa, la b requiere dos retrocesos, de 2 a 1 y luego a 0. Si te detienes después de uno, k queda en 1, aunque la b no coincide con nada, y devuelves una copia en el índice 2 que no existe.
Hacer retroceder el índice del texto de búsqueda después de una discrepancia en KMP. Solo cambia k. Hacer retroceder i vuelve a introducir el peor caso O(n · m).
Devolver dónde termina la coincidencia o un índice basado en 1. La respuesta es el inicio, contado desde 0. Las cadenas en Lua y R empiezan en 1, así que resta 1 antes de devolver el resultado.
Declarar strStr en el nivel superior en PHP. Los nombres de funciones en PHP no distinguen entre mayúsculas y minúsculas, así que entra en conflicto con la función integrada strstr. Por eso, el código inicial de PHP coloca la función en su propio espacio de nombres.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de encontrar la primera aparición de una cadena?

Comprobar cada posición inicial requiere O(n · m) tiempo en el peor caso, donde n y m son las longitudes de la cadena de búsqueda y de la cadena buscada, y O(1) de espacio adicional. El algoritmo de Knuth-Morris-Pratt requiere O(n + m) tiempo y O(m) de espacio para su tabla, independientemente de cuáles sean las letras.

¿Cómo funciona la tabla de prefijos KMP?

Para cada prefijo de la aguja, la tabla almacena la longitud de su prefijo propio más largo que también es un sufijo. Después de una discrepancia con k letras coincidentes, esas k letras son un prefijo de la aguja, y lps[k-1] indica cuántas de ellas pueden iniciar la siguiente coincidencia posible. Para aabaaab, la tabla es [0, 1, 0, 1, 2, 2, 3].

¿Por qué no usar find o indexOf, que vienen integrados?

En el código de producción deberías usarlo, ya que está probado y es rápido. Los entrevistadores plantean este problema para ver si escribes el bucle de búsqueda correspondiente con los límites correctos, y la pregunta de seguimiento habitual es cómo evitar el peor caso de O(n · m). El peor caso de una búsqueda integrada depende del lenguaje y de la versión de la biblioteca, así que no responde a esa pregunta de seguimiento.

¿Puedes resolverlo con hashing en lugar de KMP?

Sí, con el algoritmo Rabin-Karp. Calcula un hash del patrón y un hash rodante de cada ventana de m letras en el texto, actualizándolo en tiempo constante a medida que se desliza la ventana. Compara letra por letra solo cuando los hashes coinciden. Esto se ejecuta en un tiempo esperado de O(n + m), pero muchas colisiones de hash pueden hacer que vuelva a acercarse a O(n · m).

Python

def strStr(haystack, needle):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

haystack = "bananarama"
needle = "ana"

Esperado