ユニークビジョンプログラミングコンテスト2022 夏 (AtCoder Beginner Contest 268) G - Random Student ID (600)
コンテスト中の考察
ほとんどの場合はどちらの文字列が先になる可能性は半々に見える
prefixになるものがあったらそれは必ず先になる
文字列間の関係を全部見るのは$ \mathcal{O}(N^2)でできなさそう
解説の方法
Trie木を使う
木上でその文字列の前や後ろにある終了地点の数をカウントできれば良い
全ての文字列が1文字の場合は$ \mathcal{O}(|S| \times 1) = \mathcal{O}(|S|)
全ての文字列が順々にprefixになっているような関係だと$ \mathcal{O}(N) = \mathcal{O}(\sqrt{|S|})なはずなので、$ \mathcal{O}(N^2) = \mathcal{O}(|S|)