Dadas n strings, uma delas é uma substring de outra?

Suponha que recebamos uma coleção de strings, . Gostaria de saber se alguma dessas strings é uma substring de qualquer outra string da coleção. Em outras palavras, eu gostaria de um algoritmo para a seguinte tarefa: $n$ $S_1,\dots,S_n$

Entrada: $S_1,\dots,S_n$

Saída: tal que é uma subsequência de e , ou nenhum, se não, tais existem $i,j$ $S_i$ $S_j$ $i\ne j$ $i,j$

Existe um algoritmo eficiente para isso?

Se substituirmos "substring" por "prefix", existe um algoritmo eficiente (classifique as strings, faça uma varredura linear para comparar as strings adjacentes; a classificação garantirá que as substrings sejam adjacentes). Mas parece mais desafiador testar se uma string é uma substring de outra string. Um algoritmo ingênuo é iterar sobre todos os pares , mas isso requer testes de substring. Existe um algoritmo mais eficiente? $i,j$ $\Theta(n^2)$

Acho que poderíamos chamar isso de "teste de substring de todos os pares", ou algo assim.

Meu objetivo final é remover a coleção para que nenhuma string seja uma substring de qualquer outra, removendo cada uma que é uma substring de outra coisa na coleção.

Dica: matriz de sufixo.

Pseudônimo

Como observação lateral,

não está correto se você remover substrings conforme os encontra. Será menos. Além disso, você deve classificar por comprimento, pois uma sequência mais longa não pode aparecer em uma sequência mais curta. Novamente

está errado aqui.

Θ (n^{2})

$\Theta(n^2)$

Θ (n^{2})

$\Theta(n^2)$

Alexis Wilke #

@AlexisWilke,

está correto: esse é o número de testes de substring no pior caso (o pior caso é quando nenhuma string é um substring de qualquer outra). A classificação por comprimento fornece apenas um fator de dois, o que não afeta os assintóticos.

Θ (n^{2})

$\Theta(n^2)$

Respostas:

Você pode construir uma árvore de sufixos em tempo linear e verificar se há um nó interno que corresponde a uma cadeia completa (tempo constante por nó).

Mais detalhadamente, suponha que recebamos as strings . $s_1, \dots, s_n \in \Sigma^*$

Crie uma árvore de sufixos (generalizada) de com marcadores de terminal distintos em pares . $s_1\$_1, s_2\$_2, \dots, s_n\$_n$ $n$ $\$_1,\dots,\$_n \notin \Sigma$

Usando o algoritmo de Ukkonen , isso pode ser feito em tempo linear; linear na soma de todos os comprimentos de string.
Supondo que você rotule as folhas com se elas representam o sufixo de , atravesse a árvore e encontre as folhas rotuladas , ou seja, as folhas que correspondem às seqüências completas. $(i,j)$ $s_i[j..|s_i|]$ $s_i$ $n$ $(i,0)$

Isso leva tempo linear no tamanho da árvore, que é linear no tamanho da entrada.
$(i,0)$ $\$_i$ $(i,0)$

Isso novamente leva tempo linear.

Os marcadores terminais distintos não são realmente necessários; uma única usada para finalizar todas as seqüências é suficiente, desde que você permita vários rótulos por folha.

Rafael
fonte