はじめに
Herring101君のNicknameの原案に対して「それ解けるよ！」と言ったりテストケース作ったりしたKowerKointです。
この問題はwriter/tester陣それぞれでいろんな解法が出ました。
解法1(Rolling Hashを使った解法)
人$i$に対して「名字を$a$文字目までニックネームに使ったとき、名前を$b$文字採用したときに他の人の候補に被らないような最小の$b$」を求めたいです。
この発想に立ったとき、名字をソートしておけば「名字の$a$文字目まで」が重なる名前はある区間になることが使えそうだとわかります。
すべての人を予め名字でソートしておき、名前の$1$〜$|T|$文字分の接頭辞全てのハッシュを計算して「ハッシュ→その接頭辞を持つ人の番号をリストにしたもの」という辞書を作っておきます。
人$i$に対して$a$を増加させながら問題を解きます。
$a$を増やしていくと区間は単調に小さくなっていきます。
区間を$[1,N]$で初期化しておき、$a$文字を見るときに$a$文字目を見ながら区間の両端を縮めます。
区間をの左端または右端を縮める回数は$i$ごとに合計$N$回以内です。
そして、$a$を増やしていくと$b$の最小値は単調に減少します。
$b$を減少させながら、前計算した「ハッシュ→人リスト」の辞書を見ます。
リスト内で名字の条件で縮めた範囲の該当数が $1$ であればその $b$ がニックネームの条件にあっていることになります。
これは二分探索をすればいいです。
このような探索を行って各$i$に対する問題を解いていきます。
文字列全体を見なくて済むようにうまく実装することで$O(N(|S|+|T|)\log{N})$時間で解くことができる。
解法2(動的計画法を使った解法)
解説
各部員 $x$ に対して独立に答えを求めます。
dp[$i$] = ニックネームとして苗字から $i$ 文字取った場合の、ニックネーム制約を満たすために必要な名前の長さ と定義します。 配列dpを求めることができれば、答えは $\min(i + dp[i])$ と表現することができます。
まずは各部員 $i$ の苗字について、部員 $x$ の苗字との最長共通接頭辞の長さ $F_i$ を求めます。最長共通接頭辞は、予め苗字をソートして、部員 $x$ の苗字の位置を $t_x$ とすると $1,2,3, ... , t_x - 1$ 番目の最長共通接頭辞の長さが単調非減少であることから求めることができます。この部分の時間計算量は $\mathrm{O} (N + |S_i|)$ です。
次に、各部員の名前について、部員 $x$ の名前との最長共通接頭辞の長さ $X_i$ を求めます。この部分については先ほどと同様に求めることが可能です。
最後に配列dpの値を求めます。各部員 $i$ について、dp[$F_i$] = max(dp[$F_i$], $X_i$) としてテーブルを更新し、降順からdp[$i$] = max(dp[$i$],dp[$i+1$]) として最大値を更新していくことによって求めることができます。この部分の時間計算量は $\mathrm{O} (N + |S_i|)$ です。
各部員について答えを求める必要があるので、合計の時間計算量は $\mathrm{O} (N \times (N + |S_i|))$ となります。