Encontrar a subsequência de repetição mais longa

Dada uma string , eu gostaria de encontrar a subsequência mais repetida (pelo menos duas vezes). Ou seja, eu gostaria de encontrar uma string que seja uma subsequência (não precisa ser um contíguo) de tal que . Ou seja, é uma string cujas metades aparecem duas vezes seguidas. Observe que é uma subsequência de , mas não necessariamente uma substring. $s$ $w$ $s$ $w=w' \cdot w'$ $w$ $w$ $s$

Exemplos:

Para 'ababccabdc', será 'abcabc', porque 'abc' = 'abc' e 'abc' aparecem (pelo menos) duas vezes em 'ababccabdc'.

Para 'addbacddabcd', uma opção é 'dddd' porque 'dd' aparece duas vezes (não posso usar a mesma letra várias vezes, mas aqui tenho 4 'd, então está tudo bem), mas é de comprimento 4. Posso encontrar uma melhor de comprimento 8: 'abcdabcd', porque 'abcd' é uma substring de 'addbacddabcd' que aparece duas vezes.

Estou interessado em encontrar a subsequência de repetição mais longa. Isso também é chamado de "encontrar o quadrado maior / maior", mas li muitos artigos nos quais um quadrado é definido para uma substring e não para uma subsequência.

Posso usar facilmente um algoritmo de força bruta que aceitará iterando todas as opções para um ponto de interrupção na string e, em seguida, terei duas strings nas quais procurarei a maior / maior subsequência comum, mas cada verificação terá usando uma técnica de programação dinâmica; portanto, o tempo todo será . Eu encontrei um algoritmo mais eficiente para a subsequência comum mais longa que leva , portanto o tempo de execução será . $O(n^3)$ $O(n^2)$ $O(n^3)$ $O(\frac{n^2}{\log n})$ $O(\frac{n^3}{\log n})$

Estou procurando um algoritmo mais eficiente para o problema de subsequência de repetição mais longo. Talvez minha ideia de iterar em todos os pontos de interrupção desperdice muito tempo e possa ser reduzida a menos iterações. Ou talvez um algoritmo com uma atitude diferente possa resolver esse problema.

Eu pesquisei em várias revistas e perguntas anteriores, e a maioria dos resultados encontrados foram sobre uma substring e não sobre uma subsequência.

Também li que isso pode ser feito usando árvores de sufixo, mas isso também é relevante para substrings e não tenho certeza se essa ideia pode ser estendida para subsequência.

Estou procurando uma solução que seja executada no tempo . Se existir um em isso será ainda melhor (não tenho certeza se existe). $O(n^2)$ $O(n \cdot \log n)$

algorithms optimization dynamic-programming strings subsequences Dan D-man
fonte

Procure árvores com sufixo ou matrizes de sufixo.

Pseudônimo

É muito improvável que um -tempo algoritmo existe para este problema, pois se o fizesse, você pode usá-lo para bater o melhor algoritmo conhecido para encontrar o LCS de dois comprimento- cordas e como segue: Forme a string , em que é cópias de um caractere que não aparece em ou e, em seguida, execute algoritmo -time nele. Ambas as "metades" da subsequência de repetição mais longa começarão necessariamente com , então uma metade vem de cada e

o (n^{2})

$o(n^2)$

n

$n$

u

$u$

v

$v$

x u x v

$xuxv$

x

$x$

n + 1

$n+1$ $

u

$u$

v

$v$

o (n^{2})

$o(n^2)$

x

$x$

u

$u$

v

$v$ , resolvendo o problema do LCS.

Jrandom_hacker 21/02

@j_random_hacker O LCS pode ser resolvido em usando a Árvore de sufixos ou em usando hashes contínuos.

O (n + m)

$\mathcal O(n+m)$

O (n \log n)

$\mathcal O(n\log n)$

mal

@Evil: Ainda não vejo como, você poderia dar um pouco mais de detalhes? (Tem certeza de que não está pensando Longest Common Sub corda , que pode ser resolvido nas complexidades de tempo?)

j_random_hacker

@j_random_hacker Eu pensei que você está comparando objetivo com o LCS (consecutivo), mas aqui, como você mencionou, sim, eu nem vi a solução de trabalho em n ^ 2 para a Subseqüência Comum Mais Longa (eu encontrei um código de programação dinâmico, propagado por muitas páginas com falhas, semelhante à resposta reduzida). Então, simplesmente entendi mal o seu comentário, desculpe.

o (n^{2})

$o(n^2)$

Mal

Aqui está uma solução de programação dinâmica.

Suponha que a sequência de entrada seja . Crie uma tabela cujas linhas e colunas sejam indexadas por (onde é o comprimento da sequência), preenchido pela regra A resposta é . $x_1\ldots x_n$ $T$ $0,\ldots,n$ $n$

T [i, j] = {\begin{cases} 0 & if i = 0 or j = 0, \\ T [i - 1, j - 1] + 1 & if x_{i} = x_{j} and i \neq j, \\ max (T [i - 1, j], T [i, j - 1]) & otherwise . \end{cases}

$T[i,j] = \begin{cases} 0 & \text{if $i = 0$ or $j = 0$}, \\ T[i-1,j-1] + 1 & \text{if $x_i = x_j$ and $i \neq j$}, \\ \max(T[i-1,j],T[i,j-1]) & \text{otherwise}. \end{cases}$

T [n, n]

$T[n,n]$

jir17
fonte

Suponha que estamos em algum ponto com , e a condição em sua afirmação é verdadeira. Então implica que o caractere na posição faz parte de ambas as subsequências.

i, j

$i, j$

i = j + 1

$i=j+1$ ifdp[i][j] = dp[i - 1][j - 1] + 1

i - 1 = j

$i-1=j$

Jrandom_hacker

Bem-vindo à Ciência da Computação! Livre-se do código-fonte e substitua-o por idéias, pseudo-código e argumentos de correção. Veja aqui e aqui as meta-discussões relacionadas.

Raphael

@ Rafael Uma fórmula recursiva não conta como código fonte.

Number945

@BreakingBenjamin Dependendo do idioma de sua escolha, você pode anotar a recorrência especificada mais ou menos literalmente. O ponto é que não há explicação aqui.

Raphael

Encontrar a subsequência de repetição mais longa

Respostas: