Existe um subconjunto de substrings para reconstruir outra string?

Question

Eu estou procurando um algoritmo de alto desempenho para verificar se consigo reconstruir uma determinada string usando um determinado conjunto de substrings. Mais detalhes:

Vamos dizer que nossas cordas são sobre o alfabeto $ \ sigma $ .

Entradas :

• uma string $ s \ in \ sigma ^ * $
• Um conjunto finito de strings $ a={a_1, a_2, ..., a_n \} \ subconjunto \ sigma ^ * $ .

saída :

• se $ \ existe m: \ existe b_1, b_2, \ lDOTs, b_m \ em A: b_1 + b_2 + \ cdoz + b_m= s $

Onde $ + $ é concatenação de string.

Por exemplo, se $ s= {} $ " $ abcd $ " e $ a={$ << / span> " $ ab $ " $, $ << / span> " $ CD $ " $, $ " $ ac $ " $ \} $ , a resposta é verdadeira. Para os propósitos desta questão, suponha que se strings em $ a $ podem ser reutilizadas várias vezes, se necessário.

Answer 1

Se reutilizar strings na $ a $ é permitido que você possa resolvê-lo com programação dinâmica: primeiro, armazenar strings na $ Um $ em uma árvore de prefixo (apenas uma árvore de sufixo invertida link ), e Detrmine recursivamente se $ s [i: end] $ pode ser construído a partir de $ a $ : deixe $ \ ell $ Seja o comprimento da string, e o Wlog assume $ s $ é anexado por $ \ $$ e $ a \ gets a \ copo \ {\ $ \} $ . Moroaver, deixe $ m [i] \ in \ {0,1} $ indicar se $ s [i: \ ell] $ pode ser construído por elementos em $ a $ . Inicializar $ m [i] \ gets \ infty $ para $ i= 0, \ pontos, \ ell-1 $ < / span> e $ m [\ \ ell]= 1 $ (porque $ s [\ ell]=$$ < / span>). Agora, suponha $ f (i) $ é a função que calcula recursivamente $ m [i] $ se Não foi computado já. Quando $ f (i) $ é chamado, comece na raiz da árvore de sufixo da $ a $ e travessia $ s [i], s [i + 1], \ dots $ na árvore de sufixo até o índice $ j $ , de tal forma que o nó correspondente esteja em $ a $ , e chamar recursivamente $ f (j) $ . Se retorna $ 1 $ , defina $ m [i]= 1 $ e return $ 1 $ . Caso contrário, repita o processo com travessia de $ s [J + 1], S [J + 2], \ Dots $ até outro membro na matemática $ a $ , ou uma folha é alcançada. Se não houvesse sucesso, defina $ m [i]= 0 $ e return $ 0 $ . Para decidir o problema, chame $ f (1) $ . A pior complexidade do caso é a complexidade é $ \ ell d $ , com $ D $ sendo profundidade do Árvore de sufixo (sequência mais longa na $ a $ ), além do custo de construção da árvore do prefixo.

O cenário pior caso em muitos casos será evitado porque a pesquisa de chamada recursiva pára assim que uma solução for encontrada. Então, na prática, a $ \ ell d $ parte pode ser muito menor. A construção da árvore de sufixo pode ser cara dependendo da $ a $ . Mas se $ a $ é usado para várias strings $ S $ , o custo é amortizado. Se $ a $ é realmente grande e $ s $ é curto, pode ser melhor apenas classificar elementos de $ a $ e faça uma pesquisa binária em vez de travessia.