Computando a substring comum mais longa de duas seqüências usando matrizes de sufixo

Depois que aprendi a construir uma matriz de sufixos na complexidade $O(N)$ , estou interessado em descobrir os aplicativos das matrizes de sufixos. Uma delas é encontrar a substring comum mais longa entre duas strings, no tempo $O(N)$ . Encontrei na internet o seguinte algoritmo:

1. mesclar as duas seqüências $A$ e $B$ em uma seqüência $AB$
2. calcular a matriz de sufixos de $AB$
3. calcular a matriz $LCP$ (prefixo comum mais longo)
4. a resposta é o maior valor $LCP[i]$

Tentei implementá-lo, mas como muitos detalhes da implementação não foram informados (por exemplo, ao concatenar as strings, devo colocar um caractere especial entre elas ( )?), Meu código falhou em muitos casos de teste. Alguém poderia elaborar mais sobre esse algoritmo?$AcB$

Desde já, obrigado.

Nota: Eu não garanto a correção deste algoritmo; Encontrei-o em um blog e não sei se está funcionando. Se você acha que está incorreto, sugira outro algoritmo.

Seu algoritmo está incorreto . Suponho que você saiba calcular a matriz de sufixos e a matriz LCP de uma string, ou seja, sua implementação eficiente. Como foi indicado nos comentários, você deve tentar entender o que é cada componente e por que ele funciona.

Antes de mais nada, é o sufixo matriz ( ) de uma cadeia de caracteres. Uma matriz de sufixos é basicamente todos os sufixos da string S organizados em ordem lexicográfica crescente. Mais especificamente, o valor S Uma [ i ] indica que o sufixo de S a partir da posição S Uma [ i ] é classificada como i na ordenação lexicographic de todos os sufixos de S .$SA$$S$$SA[i]$$S$$SA[i]$$i$$S$

Em seguida é a matriz G C P [ i ] indica o comprimento da mais longa comum prefixo entre os sufixos começando a partir de S Uma [ i - 1 ] e S Uma [ i ] . Ou seja, ele controla o comprimento do prefixo comum mais longo entre dois sufixos consecutivos de S quando organizados em ordem lexicográfica.$LCP$$LCP[i]$$SA[i-1]$$SA[i]$$S$

Como exemplo, considere a sequência . Os sufixos em ordem lexicográfica seriam { a , a b b a b c a , a b c a , b a b c a , b b a b c a , b c a , c a } , então S A = [ 7 , $S = abbabca$$\{a, abbabca, abca, babca, bbabca, bca, ca\}$ para uma matriz indexada em 1. Amatriz L C P seria L C P = [ - , 1 , 2 , 0 , 1 , 1 , 0 ] .$SA = [7, 1, 4, 3, 2, 5, 6]$$LCP$$LCP = [-, 1, 2, 0, 1, 1, 0]$

Agora, dada duas cadeias e B , nós concatenar-los como S = A # B , onde # é um personagem não está presente em ambos A e B . A razão para a escolha de tal caráter um é para que quando o cálculo da LCP de dois sufixos, diz um b # d a b d e a b d , a comparação vai quebrar no final do primeiro string (uma vez que só ocorre uma vez, dois sufixos diferentes nunca terão na mesma posição) e não "transbordam" para a outra sequência.$A$$B$$S = A\#B$$\#$$A$$B$$ab\#dabd$$abd$

Agora, ele pode ser visto que você deve ser capaz de ver porque você só precisa ver valores consecutivos no array (o argumento é baseado em contradição eo fato de que os sufixos em S Uma estão em ordem lexicográfica). Continue verificando a matriz L C P para o valor máximo, de modo que os dois sufixos que estão sendo comparados não pertençam à mesma sequência original. Se eles não pertencerem à mesma cadeia original (uma começa em A e a outra em B ), o maior valor é o comprimento da maior substring comum.$LCP$$SA$$LCP$$A$$B$

Como exemplo, considere e B = b c . Então, S = a b c a b c # b c . Os sufixos classificados são { a b c # b c , a b c a b c # b c , b c , b c # b c , b c $A = abcabc$$B = bc$$S = abcabc\#bc$ . S $\{abc\#bc, abcabc\#bc, bc, bc\#bc, bcabc\#bc, c, c\#bc, cabc\#bc\}$
$\begin{align*} SA &= [4, 1, 8, 5, 2, 9, 6, 3, 7] \\ LCP &= [-, 3, 0, 2, 2, 0, 1, 1, 0] \end{align*}$

Agora, o maior valor é , mas é para S Um [ 1 ] e S Um [ 2 ] , sendo que ambos começar na cadeia A . Então, nós ignoramos isso. Por outro lado, G C P [ 4 ] = 2 é para S Um [ 3 ] (corresponde ao do sufixo b c de B ) e S Um [ 4 $LCP[2] = 3$$SA[1]$$SA[2]$$A$$LCP[4] = 2$$SA[3]$$bc$$B$$SA[4]$$bcabc\#bc$$A$$2$ $LCP$$SA[3]$$SA[4]$$bc$

O algoritmo que você encontrou online não está totalmente correto. Como mencionado por Paresh, falhará no exemplo dado por ele.

No entanto, se você garantir que, ao verificar o LCP, verifique apenas o LCP de substrings de cadeias diferentes. Por exemplo, se você estiver localizando o LCS das sequências A e B, precisará garantir que as entradas adjacentes da Matriz de sufixo ao verificar o LCP não sejam da mesma sequência.

Mais detalhes aqui .

Eu acho que algo como o algoritmo que você cita realmente deve funcionar se um caractere que não faz parte do conjunto de caracteres for usado como separador e as matrizes de sufixo / prefixo são criadas para excluir todas as strings que contêm o separador, provavelmente a intenção do designer. isso é basicamente equivalente à criação de matrizes de sufixo / prefixo para as duas seqüências separadas.

seria útil para referência futura se você postasse um link para o algoritmo. note que a wikipedia possui o algoritmo para isso no pseudocódigo e em muitos outros algoritmos. e há implementações na maioria dos idiomas padrão disponíveis online.