Find the First Occurrence in a String

Q: Qual é a complexidade de tempo para encontrar a primeira ocorrência de uma string?

Verificar cada posição inicial leva O(n · m) tempo no pior caso, em que n e m são os comprimentos da cadeia principal e da cadeia de busca, e usa O(1) de espaço extra. O algoritmo Knuth-Morris-Pratt leva O(n + m) tempo e O(m) de espaço para sua tabela, independentemente das letras.

FácilArrays e strings Dois ponteiros

+10

Você recebe duas strings, haystack e needle. Retorne o índice em haystack onde começa a primeira ocorrência de needle, contando a partir de 0. Se needle nunca aparecer em haystack, retorne -1. Implemente a busca você mesmo, em vez de chamar uma função integrada de busca por substring, como find ou indexOf.

Função

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

haystackstring: o texto em que pesquisar
needlestring: a string a ser procurada
Retornainteger: o índice onde começa a primeira ocorrência de needle ou -1 se não houver nenhuma

Restrições

1 ≤ haystack.length ≤ 5 × 10⁴
1 ≤ needle.length ≤ 5 × 10⁴
Ambas as strings contêm apenas letras minúsculas do inglês.
needle pode ser maior que haystack. Então, ele não pode aparecer, e a resposta é -1.

Exemplos

Entrada: haystack = "bananarama"needle = "ana"
Saída: 1
Explicação: As letras nos índices 1, 2 e 3 formam ana. Uma segunda cópia começa no índice 3 e se sobrepõe à primeira, mas a resposta é a primeira cópia, então é 1.

Entrada: haystack = "pineapple"needle = "apples"
Saída: -1
Explicação: apple começa no índice 4, e a sequência termina logo depois, então o s final da sequência de busca não tem nenhuma letra correspondente. Não existe uma cópia completa de apples, então a resposta é -1.

Entrada: haystack = "abcabcabd"needle = "abcabd"
Saída: 3
Explicação: A tentativa no índice 0 corresponde a cinco letras, abcab, e então encontra um c onde a agulha espera um d. A cópia que funciona começa no índice 3 e termina com o d final.

+16 testes ocultos ao enviar

Para ir além

Você consegue retornar todos os índices em que needle começa, incluindo cópias sobrepostas, ainda em O(n + m) de tempo?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Comparar needle em cada posição inicial está correto, mas é lento quando as correspondências quase são bem-sucedidas: uma correspondência parcial longa que falha perto do fim é descartada, e a próxima posição inicial lê novamente a maior parte das mesmas letras. O algoritmo Knuth-Morris-Pratt reaproveita esse trabalho. Uma tabela construída apenas com needle indica quanto de uma correspondência parcial que falhou ainda pode ser aproveitado, de modo que a varredura nunca volta para trás em haystack e termina em O(n + m).

Verifique cada posição inicial

Correta, mas não termina nos maiores testes

Intuição

Chame os comprimentos de n para haystack e de m para needle. Uma cópia de needle pode começar em qualquer índice de 0 a n-m. Tente essas posições iniciais da esquerda para a direita. Em cada uma, compare needle com haystack letra por letra e pare na primeira diferença. A primeira posição inicial em que todas as m letras correspondem é a resposta, e percorrer da esquerda para a direita faz com que essa seja a primeira cópia.

A última posição inicial é n-m, porque uma cópia que começasse depois ultrapassaria o fim de haystack. O mesmo limite também cobre o caso em que needle é mais longo que haystack: não há posição inicial para testar, e o loop termina retornando -1.

O custo fica evidente quando a maioria das letras corresponde. Considere um haystack de 50,000 as e um needle formado por 24,999 as seguidos de um b. Cada uma das 25,001 posições iniciais compara 25,000 letras antes de chegar ao b, o que dá mais de 6 × 10^8 comparações para uma resposta de -1.

Algoritmo

Sejam n e m os comprimentos de haystack e needle.
Para cada start de 0 a n-m, defina j como 0.
Enquanto j < m e haystack[start + j] for igual a needle[j], incremente j.
Se j atingir m, todas as letras corresponderam: retorne start.
Se nenhum início funcionar, retorne -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

Intuição

Veja o que a força bruta descarta. Ao buscar abcabd em abcabcabd, a tentativa no índice 0 corresponde a abcab e então falha. Essas cinco letras terminam em ab, e ab também é o início do padrão. Portanto, após a incompatibilidade, duas letras da próxima tentativa útil já correspondem, e você pode continuar a partir do mesmo ponto no texto.

fronteira de uma string é um prefixo mais curto que também é um sufixo, como ab em abcab. Antes da busca, crie uma tabela lps em que lps[i] é o comprimento da fronteira mais longa de needle[0..i]. Para abcabd, ela é [0, 0, 0, 1, 2, 0]. A tabela depende apenas do padrão, e você a cria com o mesmo laço de correspondência, executado com o padrão sendo comparado a si mesmo.

Em seguida, percorra o texto uma vez e mantenha k, o número de letras do padrão que corresponderam até agora. Se a próxima letra for igual a needle[k], k aumenta em um. Caso contrário, defina k como lps[k-1] e compare a mesma letra novamente, até que ela corresponda ou k seja 0. Recuar para uma fronteira nunca ignora uma ocorrência: qualquer ocorrência que comece dentro da tentativa que falhou precisa começar com uma fronteira do trecho que correspondeu, e a fronteira mais longa é testada primeiro. Quando k chega a m, a ocorrência começou em i-m+1.

Por que isso é linear: k aumenta no máximo uma vez por letra do texto, e cada recuo o diminui. Ele não pode diminuir mais vezes do que aumentou, então a varredura leva no máximo 2n passos, e a criação da tabela leva no máximo 2m.

Algoritmo

Construa lps: com k = 0, para cada i de 1 a m-1, recue com k = lps[k-1] enquanto k > 0 e needle[i] for diferente de needle[k]; se forem iguais, incremente k; armazene lps[i] = k.
Redefina k como 0 e percorra o texto principal com o índice i.
Enquanto k > 0 e haystack[i] for diferente de needle[k], defina k = lps[k-1].
Se haystack[i] for igual a needle[k], incremente k.
Se k for igual a m, retorne i-m+1. Se o laço terminar, retorne -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

Armadilhas e casos extremos

A maioria dos bugs fica no fim da haystack ou dentro do loop de fallback.

Permitir que o início avance até n-1 em vez de n-m. Quando o fim da haystack coincide com o início da needle, a comparação ultrapassa o fim de haystack, o que interrompe Python, Java, Rust e Swift com um erro de índice.
Esquecer que a needle pode ser mais longa que a haystack. Com comprimentos sem sinal, como size_t em C++ ou usize em Rust, n-m não pode ser negativo: C++ dá a volta e transforma o valor em um número enorme, e Rust entra em pânico em uma compilação de depuração. Verifique m > n primeiro ou faça o cálculo com inteiros com sinal.
Escrever o fallback do KMP como um if em vez de um while. Ao buscar aaa em aabaa, o b precisa de dois fallbacks, de 2 para 1 e depois para 0. Se parar após um, k permanece em 1, embora nada corresponda a b, e você informa uma ocorrência no índice 2 que não existe.
Recuar o índice da haystack após uma incompatibilidade no KMP. Só k muda. Recuar i traz de volta o pior caso O(n · m).
Retornar a posição em que a correspondência termina ou um índice baseado em 1. A resposta é o início, contado a partir de 0. As strings em Lua e R começam em 1, então subtraia 1 antes de retornar.
Declarar strStr no nível superior em PHP. Os nomes de funções em PHP não diferenciam maiúsculas de minúsculas, então há conflito com a função interna strstr. Por esse motivo, o código inicial de PHP coloca a função em seu próprio namespace.

Perguntas frequentes4

Qual é a complexidade de tempo para encontrar a primeira ocorrência de uma string?

Verificar cada posição inicial leva O(n · m) tempo no pior caso, em que n e m são os comprimentos da cadeia principal e da cadeia de busca, e usa O(1) de espaço extra. O algoritmo Knuth-Morris-Pratt leva O(n + m) tempo e O(m) de espaço para sua tabela, independentemente das letras.

Como funciona a tabela de prefixos do KMP?

Para cada prefixo da agulha, a tabela armazena o comprimento do seu maior prefixo próprio que também é um sufixo. Após uma incompatibilidade com k letras correspondentes, essas k letras formam um prefixo da agulha, e lps[k-1] indica quantas delas podem iniciar a próxima ocorrência possível. Para aabaaab, a tabela é [0, 1, 0, 1, 2, 2, 3].

Por que não usar o find ou o indexOf integrados?

Em código de produção, você deve usar essa opção, pois ela é testada e rápida. Os entrevistadores propõem esse problema para ver você escrever o loop de correspondência com limites corretos, e a pergunta complementar mais comum é como evitar o pior caso O(n · m). O pior caso de uma busca integrada depende da linguagem e da versão da biblioteca, então isso não responde à pergunta complementar.

Você consegue resolver isso usando hashing em vez de KMP?

Sim, com o algoritmo Rabin-Karp. Calcule um hash da sequência procurada e um hash rolante de cada janela de m letras no texto, atualizando-o em tempo constante à medida que a janela desliza. Compare letra por letra somente quando os hashes coincidirem. Isso leva O(n + m) de tempo esperado, mas muitas colisões de hash podem fazer o tempo voltar a se aproximar de O(n · m).

Python

def strStr(haystack, needle):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

haystack = "bananarama"
needle = "ana"

Esperado