Breve Non Sottosequenza Stringa Di Dimensione Costante Alfabeto

Question

Lascia $S[1..n] \in \Sigma^*$ è una stringa di $n$ simboli su di alfabeto $\Sigma$, dove $|\Sigma| \in \mathcal{O}(1)$.Determinare una stringa più corta che non possono essere ottenuti da $S$ eliminando alcuni (forse no) simboli.

Per esempio, ci è dato $\Sigma = \{ A, C, G, T \}$ e $S = ACGTACGT$.In questo caso, una valida risposta è di $CCA$, poiché non si verifica come una sottosequenza di $S$ (cioènon può essere ottenuta con la rimozione di alcuni dei simboli da $S$) e non c'è alcuna stringa di lunghezza $2$.

Sto cercando un algoritmo che prende in $\mathcal{O}(n)$ o $\mathcal{O}(n \log n)$ tempo.Non è sufficiente per calcolare la lunghezza della risposta, un esempio che dovrebbe essere costruito.

Osservazioni e Approcci. La lunghezza della risposta non superiore a $\displaystyle \frac{n}{|\Sigma|} + 1$ dal principio della piccionaia.Questo limite superiore è ottenuto per $S = ACGTACGT...ACGT$ nell'esempio di cui sopra.Se ci interessa solo la lunghezza della risposta, il seguente approccio dovrebbe funzionare.Lasciate che $f(i)$ denotano la più grande $k \in \mathbb{N}$ tale che per ogni stringa di lunghezza $k$ è una sottosequenza di il prefisso $S[1..i]$.La nostra risposta finale è $f(n) + 1$ e $f$ può essere calcolata con la programmazione dinamica in $\mathcal{O}(n)$ tempo $1 \le i \le n$, semplicemente ricorrenza

$\displaystyle f(i) = 1 + f\left(\min{(\ell(i, \sigma_1), \ell(i, \sigma_2), \dots, \ell(i, \sigma_{|\Sigma|})) - 1} ight)$

dove $\ell(i, \sigma)$ indica l'ultima occorrenza di $\sigma \in \Sigma$ il prefisso $S[1..i]$.Ovviamente, la funzione $f$ è crescente, cioè$f(i + 1) \ge f(i)$ per $1 \le i \le n - 1$.Sembra più difficile costruire un esempio da queste informazioni, che è dove mi sono bloccato.

Infine si noti che il problema è molto più semplice, se si richiede la sottosequenza non essere contigous.Poiché ci sono solo $\mathcal{O}(n^2)$ sottostringhe, ma $\mathcal{O}(|\Sigma|^k)$ stringhe di lunghezza $k$ su $\Sigma$, $k$ si rivelasse essere molto piccolo e anche il brute-force avrà successo.

Qualsiasi tipo di aiuto è apprezzato, grazie in anticipo.

Fonte Originale:I motori di ricerca personalizzati Problema (https://cses.fi/problemset/task/1087/).