Підпослідовність#44

Підпослідовність (Розбір)

Позначимо через $dp [i]$ довжину найкоротшого рядка, який не є підпослідовністю суфікса $s [i \dots n - 1]$ s[i \ldots n-1]. Відповідь — $dp [0]$ , а сам рядок відновлюється жадібно.

Спочатку побудуємо таблицю $nxt [i] [c]$ — найменша позиція $j \geq i$ j \ge i, у якій стоїть символ $c$ (або $n$ , якщо такого немає). Вона рахується одним проходом справа наліво за $O (26 n)$ .

Тепер перехід. Нехай ми будуємо рядок і перший його символ — $c$ :

якщо $c$ взагалі не трапляється в $s [i \dots]$ , то однолітерний рядок « $c$ » уже не є підпослідовністю — вартість $1$ ;
інакше нехай $p = nxt [i] [c]$ p = \mathrm{nxt}[i][c]. Жадібне вкладення підпослідовності обов'язково візьме саме цю позицію (брати пізніше входження ніколи не вигідно), тому далі задача зводиться до суфікса $s [p + 1 \dots]$ s[p+1 \ldots] — вартість $1 + dp [p + 1]$ 1 + \mathrm{dp}[p+1].

Отже,

dp [i] = c min (1 + dp [nxt [i] [c] + 1]),

\mathrm{dp}[i] = \min_{c} \bigl(1 + \mathrm{dp}[\mathrm{nxt}[i][c] + 1]\bigr),

де $dp [n + 1]$ \mathrm{dp}[n+1] вважаємо нулем (символ відсутній). База — $dp [n] = 1$ \mathrm{dp}[n] = 1.

Відновлення відповіді. Ідемо з $i = 0$ i = 0 і щоразу вибираємо найменший символ $c$ , на якому досягається мінімум. Це дає лексикографічно найменший рядок серед найкоротших: довжина вже зафіксована як оптимальна, тому серед усіх оптимальних продовжень вигідно взяти найменшу літеру, а далі міркування повторюється.

Складність — $O (26 n)$ за часом і пам'яттю; при $∣ s ∣ \leq 1 0^{5}$ |s| \le 10^5 це миттєво. Якщо пам'ять критична, таблицю $nxt$ можна не зберігати цілком, а перераховувати на льоту, ідучи справа наліво разом із динамікою.