FHC round1 25. Autocomplete

問題

distinctなN個の文字列が順番に与えられる。
自動補完機能のために、与えらえた文字列毎に1文字以上のprefixを登録しておかなければならないが、以下の条件を満たす必要がある。
i番目に与えられた文字列の登録するprefixは、
・その文字列全体
または
・i-1番目までの文字列のprefixにはなっていないprefix
「登録するprefix」の文字数の和を返す。

1<=N<=10^6

考え方

「(一般的な意味での)prefix」と「(登録する)prefix」が混乱してしまった。。

各文字列の登録するprefixはできるだけ短くしたい。
i番目の文字列は条件から、文字列の接頭辞を見て、それ以前の文字列の接頭辞になっていない最小の文字列を見つければよい。
今知りたい文字列の接頭辞が「それ以前の文字列の接頭辞」に存在するか、愚直に調べると時間がかかりすぎるため、高速に求める必要がある。

trie構造を使うと、上記を効率的に行えるのでこれを使う。
また、trie構造は、ノードをたどることで、直接、これまでの文字列のprefixになっていない最短のprefixを求めることができる。

各文字ノードについて、文字数を26文字程度、または、必要に応じて文字を登録していく方式にしないとメモリを使いつぶしてしまうので、注意。