Longest Common Substring

Q: Qual é a complexidade de tempo da maior substring comum?

A solução de programação dinâmica leva O(n × m) de tempo e O(m) de memória com uma única linha. Estender a partir de cada par de posições iniciais leva O(n × m × min(n, m)) no pior caso. Um autômato de sufixos chega a cerca de O(n + m) , ao custo de um programa muito mais longo.

Q: Como retornar a própria substring comum mais longa?

Sempre que uma célula superar best , registre também a posição i em s1 onde esse bloco termina. No final, a substring são as letras de s1 correspondentes a best que terminam nessa posição. Uma comparação estrita de maior que mantém o primeiro bloco mais longo encontrado em s1 .

MédioProgramação dinâmica

+10

Você recebe duas strings, s1 e s2. Uma substring é uma sequência ininterrupta de letras retirada de uma string, como ork de clockwork. Encontre a substring mais longa que s1 e s2 têm em comum e retorne seu comprimento. Quando nenhuma letra ocorre em ambas as strings, a resposta é 0.

Função

longestCommonSubstring(s1: string, s2: string) → integer

s1string: a primeira string
s2string: a segunda string
Retornainteger: o comprimento do maior bloco de letras encontrado em ambas as strings

Restrições

1 ≤ s1.length ≤ 1000
1 ≤ s2.length ≤ 1000
s1 e s2 são compostas por letras minúsculas do inglês.

Exemplos

Entrada: s1 = "clockwork"s2 = "workshop"
Saída: 4
Explicação: work fecha clockwork e abre workshop, então é uma substring comum de comprimento 4, e nenhum bloco mais longo aparece em ambos.

Entrada: s1 = "hammer"s2 = "harmed"
Saída: 2
Explicação: ha e me ocorrem nas duas palavras, mas não há uma sequência de três letras. As duas palavras contêm h, a, m, e nessa ordem, mas harmed tem um r entre o a e o m.

Para ir além

Você consegue testar se existe uma substring comum de comprimento L em cerca de O(n + m) de tempo usando um hash rolante e, em seguida, fazer uma busca binária em L?

Dicas

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

0 de 3 abertas

Solução

Estender uma correspondência a partir de cada par de posições iniciais relê as mesmas letras. Em vez disso, observe onde um bloco termina: o bloco comum que termina em s1[i] e s2[j] tem uma letra a mais que o bloco que termina nas duas letras anteriores a elas, ou é vazio se as letras forem diferentes. Uma tabela desses comprimentos responde em O(n × m) tempo.

Estenda a partir de cada par de posições iniciais

Correta, mas não termina nos maiores testes

Intuição

Toda substring comum começa em alguma posição i de s1 e em alguma posição j de s2. Para cada par, avance enquanto as letras forem iguais e conte os passos; a maior contagem é a resposta.

Textos repetitivos tornam os percursos longos. Quando ambas as strings têm 1000 cópias de a, cada par percorre até o fim do sufixo mais curto: cerca de 3.3 × 10^8 comparações de letras. O percurso a partir de (i, j) repete todo o percurso a partir de (i+1, j+1), uma letra depois.

Algoritmo

Defina best = 0.
Para cada i em s1 e cada j em s2, defina k = 0.
Enquanto i+k e j+k estiverem dentro de suas strings e s1[i+k] == s2[j+k], some 1 a k.
Mantenha o maior k em best e retorne-o.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    best = 0
    for i in range(n):
        for j in range(m):
            # Walk forward while the two strings agree
            k = 0
            while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
                k += 1
            if k > best:
                best = k
    return best

Tabela dos comprimentos dos blocos que terminam em cada par

Intuição

Seja run[i][j] o comprimento do maior bloco comum que termina exatamente em s1[i-1] e s2[j-1]; a linha 0 e a coluna 0 contêm 0. Esse bloco deve conter ambas as letras. Se forem diferentes, não existe bloco e a célula é 0. Se forem iguais, o bloco é esse par mais o bloco que termina uma letra antes em ambas as strings: run[i-1][j-1] + 1. Toda substring comum termina em algum lugar, então a resposta é a célula maior, onde quer que ela esteja.

Para hammer e harmed, os h dão 1 e os a estendem para 2; então o r interrompe o bloco. O segundo m de hammer encontra o m de harmed após uma incompatibilidade entre m e r, então começa em 1, e os e elevam o valor para 2. Nenhuma célula chega a 3.

Uma comparação por célula: cerca de um milhão para duas strings de 1000 letras, qualquer que seja o texto.

Algoritmo

Inicialize run com n+1 linhas e m+1 colunas, todas com 0, e defina best = 0.
Percorra i de 1 a n e, dentro desse loop, j de 1 a m, comparando s1[i-1] com s2[j-1].
Em caso de correspondência, defina run[i][j] = run[i-1][j-1] + 1 e atualize best.
Em caso de divergência, deixe a célula como 0.
Retorne best.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    # run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
    run = [[0] * (m + 1) for _ in range(n + 1)]
    best = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                run[i][j] = run[i - 1][j - 1] + 1
                if run[i][j] > best:
                    best = run[i][j]
            # a mismatch leaves run[i][j] at 0
    return best

Uma linha, atualizada da direita para a esquerda

Intuição

Cada célula lê apenas a célula na diagonal acima e à esquerda. Portanto, um array run de m+1 números pode armazenar a tabela se você percorrer j da direita para a esquerda: quando você grava run[j], a posição run[j-1] ainda contém o valor da letra anterior de s1, que é a célula diagonal.

Agora, uma incompatibilidade precisa gravar 0 explicitamente, pois a posição ainda contém um número da linha anterior. O tempo continua sendo O(n × m), e a memória cai de cerca de 10^6 números para 1001.

Algoritmo

Crie um array run com m+1 zeros e defina best = 0.
Para cada letra ch de s1, percorra j de m até 1.
Se ch == s2[j-1], defina run[j] = run[j-1] + 1 e atualize best.
Caso contrário, defina run[j] = 0.
Retorne best.

def longestCommonSubstring(s1, s2):
    m = len(s2)
    # run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
    run = [0] * (m + 1)
    best = 0
    for ch in s1:
        # Right to left, so run[j-1] still holds the value from the previous letter of s1
        for j in range(m, 0, -1):
            if ch == s2[j - 1]:
                run[j] = run[j - 1] + 1
                if run[j] > best:
                    best = run[j]
            else:
                run[j] = 0
    return best

Armadilhas e casos extremos

Retornar a última célula. run[n][m] cobre apenas blocos que terminam nas últimas letras de ambas as strings. Para abc e abd, o resultado é 0, enquanto para ab é 2.
Copiar o vizinho maior quando há uma incompatibilidade. Essa é a regra da subsequência, que permite que um bloco pule letras: para hammer e harmed, ela retorna 4 em vez de 2.
Percorrer a linha única da esquerda para a direita. O valor da diagonal é sobrescrito antes de ser lido, então a comparado com aa resulta em 2.
Pular a reinicialização na linha única. Um comprimento da letra anterior de s1 persiste e depois estende um bloco que não existe.
Percorrer a força bruta sem verificar os limites. Para zzzz comparado com zz, o código lê além do fim da string mais curta.

Perguntas frequentes3

Qual é a diferença entre a maior substring comum e a maior subsequência comum?

Uma substring é uma sequência contínua de letras; uma subsequência mantém a ordem, mas pode ter lacunas. Para hammer e harmed, a substring comum mais longa tem comprimento 2, e a subsequência comum mais longa tem comprimento 4 (hame). Nas tabelas, uma incompatibilidade redefine a célula da substring para 0, mas faz com que a célula da subsequência copie o maior dos valores vizinhos.

Qual é a complexidade de tempo da maior substring comum?

A solução de programação dinâmica leva O(n × m) de tempo e O(m) de memória com uma única linha. Estender a partir de cada par de posições iniciais leva O(n × m × min(n, m)) no pior caso. Um autômato de sufixos chega a cerca de O(n + m), ao custo de um programa muito mais longo.

Como retornar a própria substring comum mais longa?

Sempre que uma célula superar best, registre também a posição i em s1 onde esse bloco termina. No final, a substring são as letras de s1 correspondentes a best que terminam nessa posição. Uma comparação estrita de maior que mantém o primeiro bloco mais longo encontrado em s1.

def longestCommonSubstring(s1, s2):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

s1 = "clockwork"
s2 = "workshop"

Saída Esperada

Longest Common Substring

Função

Restrições

Exemplos

Dicas

Solução

Estenda a partir de cada par de posições iniciais

Tabela dos comprimentos dos blocos que terminam em cada par

Uma linha, atualizada da direita para a esquerda

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos