Maior sequência repetida (dispersa) em uma seqüência de caracteres

26

Declaração informal do problema:

Dada uma sequência, por exemplo, ACCABBAB , queremos colorir algumas letras em vermelho e outras em azul (e algumas nem sequer), de modo que a leitura apenas das letras vermelhas da esquerda para a direita produz o mesmo resultado que a leitura apenas as letras azuis.

No exemplo, poderíamos pintá-los assim: ACCABBAB

Portanto, dizemos CAB é uma subsequência de repetição de uma ACCABBAB . É também a subsequência repetida mais longa (fácil de verificar).

Podemos calcular as subsequências repetidas mais longas com eficiência?

Pergunta formal:

É NP-difícil decidir por uma string e algum k , se existe uma subsequência repetida de comprimento k na string?

  • Em caso afirmativo: Qual problema pode ser reduzido para esse problema?
  • Caso contrário: o que é um algoritmo eficiente? (obviamente, esse algoritmo pode ser usado para calcular a subsequência repetida mais longa)

Pergunta bônus:

Será sempre uma subsequência repetida de comprimento n/2o(n) se o tamanho do alfabeto for limitado por uma constante?

(Isso é conhecido por alfabetos binários.)

Edição 2: a resposta negativa à pergunta sobre bônus já é conhecida por alfabetos de tamanho mínimo de . Na verdade para alfabetos de tamanho Σ , existem cadeias mais longas com subsequências repetidas de um comprimento de apenas S ( n · Σ - 1 / 2 )5ΣO(n·Σ1/2) . Sequências aleatórias são suficientes para mostrar isso. O resultado já existia, mas eu o ignorei.

Editar: Nota:

Algumas pessoas querem dizer "substring" quando dizem "subsequence". Eu não. Este não é o problema de encontrar uma substrings duas vezes.

Sekti
fonte
Sekti, obrigado. Você está certo: meu primeiro comentário foi errado; Eu o apaguei agora. Por outro lado, meu comentário restante é sobre subsequências não contíguas. Se for corrigido, existe uma maneira de resolver seu problema (com subsequências não contíguas, mandatadas para não se sobrepor) em O ( n 2 k + 2 ) ou mais. Cada subproblema dp controla os índices de todas as letras vermelhas e todas as letras azuis escolhidas até o momento. Provavelmente isso não é interessante, porque não nos diz o que acontece quando k faz parte da entrada. kO(n2k+2)k
DW
@DW Por que a pergunta formal não pode ser respondida com eficiência com esta modificação da subsequência comum mais longa? Talvez esteja faltando alguma coisa e alguém possa me esclarecer.
Bryce Kille 24/04
@BryceKille, eu não sei; talvez possa. Se você descobrir como fazê-lo, espero que você escreva uma resposta!
DW

Respostas:

-2

Isso pode ser resolvido em tempo polinomialconstruindo um gráfico onde cada nó representa um ponto ( i , j ) em alguma subsequência repetida de S, de modo que S [ i ] = S [ j ] . Borda entre os nós u e v significa que u pode ser continuado por v para formar uma subsequência repetida de comprimento 2.G(i,j)SS[i]=S[j]uvuv

1. Encontre os nós. Isso pode ser feito em , criando uma lista classificada de índices para cada caractere c e depois enumerando os pares exclusivos. Não há mais que m = n 2 nós.O(n2)cm=n2

2. Encontre as arestas. Leva tempo para verificar se o nó u pode ser continuado pelo nó v , portanto, considerando todos os pares ( u , v ), essa etapa leva tempo O ( m 2 ) .O(1)uv(u,v)O(m2)

3. Observe que o caminho mais longo em pode não ser uma subsequência repetida válida. Considere os caminhos a b e b c . Se existe uma aresta a c, então a b c é uma subsequência repetida válida de comprimento 3. Portanto, leva O ( m 4 ) tempo para encontrar todas as subsequências repetidas de comprimento 3. No caso geral, leva tempo linear para verificar se duas caminhos válidos de comprimento n podem ser combinados em um caminho válido de comprimento n + 1 .GabbcacabcO(m4)nn+1

4. Itere a etapa 3 até que não sejam mais encontrados caminhos.

noplogist
fonte
Hmm. Muito rápido. Na etapa 3, o número de subsequências a serem consideradas aumenta cada vez mais. Portanto, não é polinomial.
Noplogist
1
Bem-vindo ao CS.SE e obrigado por tentar resolver esse problema! Receio não entender seu algoritmo. O que é o passo 3? Tudo o que vejo em "3." são algumas declarações / observações declarativas, mas não vejo uma especificação processual do que o algoritmo deve fazer. Além disso, não vejo o que significa iterar a Etapa 3 ou a justificativa para sua afirmação de queO(nnm2)o tempo é suficiente. Seu comentário subsequente faz parecer que você não acredita mais que sua resposta está correta. Nesse caso, talvez seja melhor excluir a resposta, para evitar confusão.
DW
Você sempre pode cancelar a exclusão ou postar uma nova resposta se descobrir a resposta mais tarde.
DW
DW, obrigado. A entrada para a etapa 3 é todas as subsequências repetidas de comprimento n e a saída é todas as subsequências repetidas de comprimento n + 1. Eu acredito que o algoritmo está correto, mas que não é um algoritmo de tempo polinomial. Marquei as reivindicações que considero incorretas.
Noplogist
Obrigado. Compreendo. Infelizmente, com essas revisões, receio que essa resposta não responda à pergunta que foi feita. A pergunta era: isso é difícil para o NP? Existe um algoritmo eficiente? Mostrar que existe um algoritmo de tempo exponencial não ajuda a responder a nenhuma dessas perguntas. De fato, já é trivial ver que existe um algoritmo de tempo exponencial para o problema, sem invocar nenhuma técnica sofisticada. Agradeço sua tentativa.
DW