Esiste un sottoinsieme di sottostringhe per ricostruire un'altra stringa?

Question

Sto cercando un algoritmo ad alte prestazioni per verificare se posso ricostruire una determinata stringa utilizzando un dato insieme di sottostringhe.Più dettagli:

Diciamo che le nostre corde sono sopra l'alfabeto $\Sigma$.

Ingressi:

• Una stringa $S \in \Sigma^*$
• Un insieme finito di stringhe $A = \{a_1, a_2, ..., a_n\} \subset \Sigma^*$.

Produzione:

• Se $\esiste m:\esiste b_1, b_2, \ldots, b_m \in A:b_1+b_2+\cpunti+b_m = S$

Dove $+$ è la concatenazione di stringhe.

Ad esempio, se $S={}$"$abcd$" E $A = \{$"$ab$"$,$"$cd$"$,$"$ac$"$\}$, la risposta è vera.Ai fini di questa domanda, supponiamo che le stringhe in $A$ può essere riutilizzato più volte se necessario.

Answer 1

Se si riutilizzano le stringhe in $A$ è consentito puoi risolverlo con la programmazione dinamica:Per prima cosa, memorizza le stringhe $A$ in un albero di prefissi (solo un albero di suffissi invertiti collegamento) e determinare ricorsivamente se $S[i:fine]$ può essere costruito da $A$:Permettere $\ell$ essere la lunghezza della stringa e assumere wlog $S$ è aggiunto da $\$$ E $A\prende A\coppa \{\$\}$.Inoltre, lasciamo $m[i]\in\{0,1\}$ indicare se $S[i:\ell]$ può essere costruito da elementi in $A$.Inizializzare $m[i]\ottiene \infty$ per $i=0,\punti, \ell-1$ E $m[\ell]=1$ (Perché $S[\ell]=\$$).Ora, supponiamo $f(i)$ è la funzione che calcola ricorsivamente $m[i]$ se non è già stato calcolato.Quando $f(i)$ si chiama, inizia dalla radice dell'albero del suffisso di $A$, e attraversare $S[i], S[i+1], \dots$ sull'albero dei suffissi fino all'indice $j$ , in modo tale che il nodo corrispondente sia dentro $A$, e chiamare ricorsivamente $f(j)$.Se ritorna $1$, impostato $m[i]=1$ e ritorno $1$.Altrimenti, ripetere il processo con attraversamento di $S[j+1], S[j+2], \dots$ finché non entra un altro membro $A$, o viene raggiunta una foglia.Se non c'è stato successo, imposta $m[i]=0$ e ritorno $0$.Per decidere il problema, chiamare $f(1)$.La complessità del caso peggiore è la complessità $\ell d$, con $d$ essendo la profondità dell'albero dei suffissi (sequenza più lunga in $A$), più il costo di costruzione dell'albero dei prefissi.

Lo scenario peggiore in molti casi verrà evitato perché la ricerca ricorsiva delle chiamate si interrompe non appena viene trovata una soluzione.Quindi, in pratica, il $\ell d$ la parte potrebbe essere molto inferiore.La costruzione dell'albero dei suffissi può essere costosa a seconda $A$.Ma se $A$ viene utilizzato per più stringhe $S$, il costo viene ammortizzato.Se $A$ è davvero grande e $S$ è breve, potrebbe essere meglio ordinare semplicemente gli elementi di $A$ ed eseguire una ricerca binaria invece di un attraversamento.