問題概要
英小文字からなる $n$ 個の文字列 $S_1, S_2, \dots, S_n$ が与えられる．
$k = 1,2, \dots, n$ それぞれについて，以下の問題を解け：
- $T \leftarrow S_k$ とする．
- $T$ に対し，以下の操作のいずれかを任意の回数適用できる：
- $T$ が空でないとき，$T$ の末尾の文字を削除する．
- 英小文字 $c$ を任意に選び，$T$ の末尾に $c$ を追加する．
- $T$ を空文字列もしくは $S_1, S_2, \dots, S_{ k - 1 }$ のいずれかと一致させるための操作回数の最小値はいくらか？
制約
- $1 \leq n \leq 2 \times 10^5$
- $1 \leq | S_i |$
- $\sum\limits_{ i \in \{ 1, 2, \dots, n \} } | S_i | \leq 2 \times 10^5$
解法
文字列 $S$ に対し，$S$ の先頭 $i$ 文字を取り出してできる文字列を $P_S( i )$ と書くことにします．$P_S( 0 )$ は空文字列です．なお，このような文字列は $S$ の接頭辞 (prefix) と呼ばれます．
わざわざ追加した文字を後から削除しても新たな文字列*1は作れないので，操作は何回か（$0$ 回でもよい）の削除操作→何回か（これまた $0$ 回でもよい）の追加操作の順になります．なので，ある $k$ について条件を満たすための操作の流れは，
- $t$ 回の操作により，$S_1, S_2, \dots, S_{ k - 1 }$ のいずれかの接頭辞であるような $P_S( |T| - t )$ を得る．この文字列を $T'$ とする．
- $T'$ が空文字列なら，手順 1. の $t$ 回の操作で達成．
- そうでないとき，$T'$ が接頭辞であるような $S_i$ の内で最も短いものを $S'$ として，$t$ に加えて $| S' | - | T' |$ 回の操作で $T'$ を $S'$ に一致させることで達成．
となります．上記手順による操作回数の内，最小のものが答えです．手順 2. によって目標を達成する場合の操作回数は明らかに $|T|$ なので，これはすぐに求まります．よって，空でない接頭辞を作ってから $\{ S_1, S_2, \dots, S_{ k - 1 } \}$ のいずれかの元に一致させるための操作回数を求めることが問題になります．
知識の話として，文字列の集合 $\mathcal S$ に対して別途与えられる文字列を接頭辞にもつ文字列が含まれるか否かを判定できるデータ構造として Trie (prefix tree) があります．$\mathcal S$ に対応する Trie を $\mathcal T_{ \mathcal S }$ とします．$\mathcal T_{ \mathcal S }$ は，各ノードが $\mathcal S$ のいずれかの元の接頭辞になっているような文字列に対応する根付き木で，根は空文字列に対応します．また，文字列 $S$ に対応するノードがあるとき，各文字 $c$ について $S + c$ に対応するノードを（それが $\mathcal S$ の元の接頭辞のとき）子にもちます．
Trie $\mathcal T$ に対し，文字列 $S$ に対応するノードが $\mathcal T$ にあることを $S \in \mathcal T$ と書くことにします．
解こうとしている問題の話に戻ります．ある $k$ に対し，$\mathcal S = \{ S_1, S_2, \dots, S_{ k - 1 } \}$ とします．空でない $T' = P_{ S_k }( i )$ に対してそれを $\mathcal S$ のいずれかの元に一致させるコストは，
- $T' \not \in \mathcal T_{ \mathcal S }$ のとき，不可能なので番兵的に $\infty$．
- そうでないとき，$T'$ に対応するノードの子孫であって $T'$ に対応するノードに最も近い，$\mathcal S$ の元に対応するノードまでの距離．
となります．後者を計算するために，Trie の各ノードに追加のデータ $h$ をもたせます．各ノードにおいて $h$ は，
- そのノードが $\mathcal S$ の元であるとき $0$．
- そうでないとき，そのノードの子ノードの集合を $\mathrm{ CH }$ として $\min\limits_{ c \in \mathit{ CH } } c{.}h$．
となります．各ノードの $h$ は，Trie に文字列を追加するときにその文字列に対応するノードで $h \leftarrow 0$ とし，その祖先について下*2から順に $h$ を更新すれば計算できます．また，$T'$ としてとる文字列を長さの昇順に試していくことにすれば，$T$ に沿って $\mathcal T_{ \mathcal S }$ を潜っていくことに対応するので，（$\min$ とかの）計算に必要な値は $O( |T| )$ 時間で集まります．
以上から，各 $S_k$ について，
- 答えの計算に $O( | S_k | )$ 時間
- Trie に $S_k$ を追加するのに $\Theta( | S_k | )$ 時間
のアルゴリズムが得られました．制約から全体の時間計算量は $O\left( \sum\limits_{ i \in \{ 1, 2, \dots, n \} } | S_i | \right)$ 時間となり，問題に正答できます．
コード
#include <memory> constexpr auto INF = LIM<>::max() / 2; struct Trie { struct Node { VT< unique_ptr< Node > > children; int highest_leaf = INF; Node() : children( 26 ) { return; } void add( const string &S, const int i = 0 ) { if ( i == SZ( S ) ) { highest_leaf = 0; return; } auto &child = children[ S[i] - 'a' ]; if ( !child ) { child = make_unique< Node >(); } child->add( S, i + 1 ); chmin( highest_leaf, child->highest_leaf + 1 ); return; } int mincost( const string &S, const int i = 0 ) { if ( i == SZ( S ) ) { return highest_leaf; } const int res = i == 0 ? SZ( S ) : SZ( S ) - i + highest_leaf; const auto &child = children[ S[i] - 'a' ]; return child ? min( res, child->mincost( S, i + 1 ) ) : res; } }; unique_ptr< Node > root; Trie() : root( make_unique< Node >() ) { return; } void add( const string &S ) { root->add( S ); return; } int mincost( const string &S ) { return root->mincost( S ); } }; int main() { IN( int, N ); Trie trie; REP( N ) { IN( string, S ); cout << trie.mincost( S ) << '\n'; trie.add( S ); } cout << flush; return 0; }
