Subseqüência de uma string, mas não de outras

Seja um alfabeto e sejam cadeias de caracteres sobre esse alfabeto. Chame uma string good se for uma subsequência de mas não uma subsequência de nenhuma de . $\Sigma$ $x^+,x^-_1,\dots,x^-_n \in \Sigma^*$ $s \in \Sigma^*$ $s$ $x^+$ $x^-_1,\dots,x^-_n$

Dado , estou procurando encontrar a menor string boa . Existe um algoritmo razoável para isso? Estou interessado em um algoritmo prático, mesmo que seu pior caso de execução não seja grande. No meu domínio, as strings podem ser razoavelmente longas, mas espero que exista uma boa string que seja bastante curta, caso isso ajude. $x^+,x^-_1,\dots,x^-_n$ $s$ $x^+,x^-_1,\dots,x^-_n$ $s$

O caso é tratado pela sub-sequência Mais curta de uma sequência, que não é uma sub-sequência de outra sequência , mas preciso lidar com o caso . $n=1$ $n>1$

algorithms regular-languages strings substrings subsequences DW
fonte

Minha proposta padrão: árvore de sufixos? A string que você está procurando é o nó com o menor nível entre todos os que têm apenas como folha. Oh, espera ... sub sequência ? Droga. Hum.

(x^{+},_)

$(x^+, \_)$

Raphael

Esse problema sem a subsequência comum dupla à mais longa? Nesse caso, talvez algo possa ser feito nesse sentido. (Enumerar não-subsequências comuns aumentando o tamanho da solução resolveria seu problema.)

x^{+}

$x^+$

Raphael

Acredito que DP de Aryabhata pode ser estendido facilmente ao caso: uso apenas tabelas, uma para cada , e depois caça para o menor tal que para cada tabela , e por algum , . Isso irá dizer-lhe o comprimento ( ) e o caráter final ( ), mas eu ainda não tenho certeza de como extrair os personagens anteriores ...

n > 1

$n > 1$

n

$n$

x_{i}^{-}

$x_i^-$

L

$L$ $i$

k

$k$

i s_t h e r e [i, k, t, L] = f a l s e

$is\_there[i, k, t, L] = false$

L

$L$

x^{+} [k]

$x^+[k]$

j_random_hacker

@j_random_hacker, acho que não funciona. Isso pode escolher uma subsequência de de comprimento que não seja uma subsequência de e uma subsequência diferente de de comprimento que não seja uma subsequência de . (O primeiro pode ser uma subsequência de e o segundo uma subsequência de , o que seria ruim.) Precisamos de uma única subsequência de , não de uma separada para cada . Ou eu perdi algo inteligente sobre a sua ideia?

x^{+}

$x^+$

L

$L$

x_{1}^{-}

$x^-_1$

x^{+}

$x^+$

L

$L$

x_{2}^{-}

$x^-_2$

x_{2}^{-}

$x^-_2$

x_{1}^{-}

$x^-_1$

x^{+}

$x^+$

x_{i}^{-}

$x^-_i$

Se você não precisa absolutamente da subsequência mais curta, pode usar o fato de que, se uma string não for uma subsequência de nenhum , também não será uma subsequência de nenhuma intercalação das strings . Portanto, você pode tentar várias maneiras diferentes de intercalar aleatoriamente as seqüências em uma única string e, para cada intercalação , procurar uma subsequência de que evite ser uma subsequência de usando o DP de Aryabhata e escolher o que for menor que .

s

$s$

x_{i}^{-}

$x_i^-$

x_{i}^{-}

$x_i^-$

n

$n$

x_{i}^{-}

$x_i^-$

y_{j}

$y_j$

z_{j}

$z_j$

x^{+}

$x^+$

y_{j}

$y_j$

z_{j}

$z_j$

Jrandom_hacker 31/08

Respostas:

Erros

Em primeiro lugar, nos comentários cometi alguns erros: tanto a reivindicação original que fiz sobre a intercalação como o comentário "corrigindo" (agora excluído) estavam erradas, e separadamente a minha alegação de que tentar todas as intercalações possíveis deve produzir uma solução ideal também estava errado (dou um contra-exemplo simples abaixo). Finalmente, minha sugestão para definir e iterar, ou usar a pesquisa por feixe, também não ajuda: qualquer resposta que possa ser produzida com isso e a aplicação do DP de Aryabhata nunca pode ser melhor do que usar o , pois tudo o que faz é reduzir o tamanho do conjunto de soluções a partir do qual o DP pode escolher. Desculpa! Esperamos que a versão melhorada abaixo não contenha mais problemas ... $x^+ = z_j$ $x^+$

Também notei dois erros no DP de Aryabhata . Felizmente, ambos podem ser facilmente reparados (veja meus comentários nesse post).

Uma solução heurística usando intercalações aleatórias

Se você não precisar absolutamente da subsequência mais curta, poderá usar o fato de que, se uma string for uma subsequência de algum , também será uma subsequência de toda intercalação possível de todas as strings . Por outro lado, se não é uma subsequência de alguma intercalação particular de todas as cadeias , então não é uma subsequência de nenhum indivíduo . $s$ $x^-_i$ $x^-_i$ $s$ $x^-_i$ $x^-_i$

Portanto, você pode tentar muitas maneiras diferentes de intercalar aleatoriamente as seqüências em uma única string e, para cada intercalação , procure a subsequência mais curta de que evita ser uma subsequência de usando o bom DP de Aryabhata algoritmo para o caso de duas cordas e escolha o menor que seja o mais curto entre todas as intercalações que você tentou. $n$ $x^−_i$ $y_j$ $z_j$ $x^+$ $y_j$ $z_j$

Advertência: Não há garantia de otimização, mesmo se tentarmos todas as intercalações

Surpreendentemente (pelo menos para mim), mesmo se você repetir o procedimento acima para todas as intercalações possíveis, não há garantia de encontrar a solução ideal: considere a instância em que , e . Então é uma solução ideal com comprimento 2, mas a solução mais curta encontrada ao tentar todas as intercalações de e é , com comprimento 3. $x^+ = aaa$ $n=2$ $x^-_1 = x^-_2 = a$ $aa$ $x^-_1$ $x^-_2$ $aaa$

j_random_hacker
fonte