Subseqüência mais comum

Uma string possui subsequências, mas elas geralmente não são todas distintas. Qual é a complexidade de encontrar a frequência máxima de qualquer subsequência? $2^n$

Por exemplo, a string "subsequence" contém 7 cópias da subsequence "sue" e esse é o máximo.

Exemplo de código de força bruta em http://ideone.com/UIp3t

Existem teoremas estruturais relacionados? Ambos acabam sendo falsos :

a mais longa das subsequências de frequência máxima é única
a frequência máxima de qualquer subsequência de comprimento é unimodal em $k$ $k$

Possivelmente links relacionados:

Contando # subsequências distintas http://11011110.livejournal.com/254164.html $\in \mathbf{P}$
Problema de concurso relacionado para várias fontes http://www.spoj.pl/problems/CSUBSEQS/
Artigo relacionado http://dx.doi.org/10.1016/j.tcs.2008.08.035

Edite 10 dias depois: obrigado por dar uma olhada! Eu me perguntava se isso seria um bom problema de concurso de programação solucionável em tempo polinomial. Acho que não, mas espero pensar novamente mais tarde.

ds.algorithms string-search daveagp
fonte

Uma pergunta inicial possivelmente ingênua: está claro que esse problema está no PN ? Ou seja: para o problema de determinar se há uma subsequência com pelo menos k ocorrências em uma cadeia de caracteres n , como seria um certificado? Por exemplo, listar todas as tuplas de índices indicando as instâncias de uma determinada subsequência falharia em ter tamanho polinomial para a cadeia aaa ... aa (que, embora seja uma entrada chata, ainda assim possui uma subcadeia com aproximadamente

ocorrências).

n C (n / 2)

$n \mathbf C (n/2)$

Niel de Beaudrap 15/08/12

@Niel de Beaudrap: Acho que podemos contar o número de ocorrências como subsequências no tempo polinomial por meio de programação dinâmica, possibilitando o uso da subsequência em si como um certificado.

Tsuyoshi Ito

Estou um pouco confuso: a pergunta "dada uma string s, encontra a subsequência que ocorre o número máximo de vezes?"

Suresh Venkat

n

$n$

n / 2

$n/2$

@ marzio-de-biasi: a questão à qual você se vinculou é diferente (e muito mais fácil): aí você recebe a subsequência.

David

Respostas:

de uma pesquisa, aqui está um artigo com algumas pesquisas e descobertas para pesquisas em nível de pós-graduação, mas (ressalva) sem referências. possui algumas heurísticas, estimativas, resultados empíricos e comentários sobre o problema e algumas idéias para provar sua complexidade (aproximação) etc.

Identificação das subsequentes mais frequentes
Relatório final do projeto de biologia computacional CSE 549
Mikhail Bautin 2006

(embora existam alguns problemas padrão de subsequência que são um pouco semelhantes e estudados, por exemplo, no artigo de Elzinga et al., é possível que esse problema de subsequência específico não tenha sido estudado muito?)

vzn
fonte

Não entendo por que isso foi rebaixado. Pode não ser um artigo muito profundo, mas parece estar diretamente relacionado ao tópico.

David Eppstein

fyi / adendo Bautin também diz no final de papel que ele tem 5K linhas de código C ++ e Python sobre o problema / papel para todos os interessados

vzn

@ David, eu não acho que o voto negativo seja por causa do artigo vinculado, provavelmente está mais relacionado ao fato de que essa resposta parece (essencialmente) uma resposta de link de uma linha (sem explicar como o artigo está relacionado à pergunta). e responde). Isso pode ter sido mais apropriado como um comentário.

Kaveh

ok kaveh, então, explicitado: o jornal parece revelar (a menos que alguém possa encontrar uma referência melhor ou apresentar uma prova desse problema difícil) que a complexidade exata do problema é até agora desconhecida / aberta (exceto a óbvia PSPACE / EXPTIME) e pode conter a melhor análise conhecido / abordagens para resolvê-lo tão longe

vzn

Eu encontrei este artigo antes e peço desculpas por não ter vinculado a ele acima, o que foi porque eu não achei que ele desse muita informação concreta. Enviei um e-mail ao autor há algum tempo, perguntando se havia mais algo a dizer sobre algo que aconteceu desde que foi escrito, mas ainda não obtive resposta.

Daveagp

Não é uma resposta, apenas um lema.

${n+k-\lceil k/t\rceil \choose k}={n+k-\lceil k/t\rceil \choose n-\lceil k/t\rceil}$ $t$ $k$ $t$

domotorp
fonte