文字列 \(T\) の長さを \(|T|\) と表します。\(\sum |S_i|\) を \(L\) とします。

各文字列 \(S_i\) に対して、\(S_i\) の周期かつ\(|S_i|\)の約数である最小のもの \(p_i\) を求め、\(S_i\) の先頭から \(p_i\) 文字目までからなる文字列を \(T_i\) とします。
例えば \(S_i=\) abcabcabc に対しては \(T_i=\) abc となり、\(S_i=\) ababa に対しては \(T_i=\) ababa となります。
この \(p_i,T_i\) を求めることは、Z-algorithm を用いることで \(O(|S_i|)\) 時間で行えます。

\(T_i\) が異なる人のあだ名の候補が等しくなることはありません。したがって、\(T_i\) ごとに人を分類して独立に考えて良いです。

\(T_i\) ごとに分類したあとの問題を考えます。すなわち、全ての \(i\) で \(T_i\) が等しいときを考えます。このとき、あだ名が重複するかどうかは文字列長のみにより判断することができます。しがたって、すでにつけたあだ名の文字列長の集合を持つことで、次の問題が解ければ十分です。

空の正整数の集合 \(X\) に対して以下のクエリを高速に処理せよ

• \(n\) が与えられる。\(X\) に含まれていない最小の \(n\) の倍数を求めて出力し、それを \(X\) に追加する

この問題は、\(n\) ごとに以前のクエリに対する答えをメモしておき、次のクエリではその続きから愚直に調べることで、全体で \(O(L (\log L)^2)\) で解くことができます。

よって以上により \(O(L(\log L)^2)\) でこの問題を解くことができました。

Writer解(C++)

ローリングハッシュを使った解法

元の問題を愚直に定式化すると次のようになります。

空の文字列の集合 \(X\) に対して以下のクエリを高速に処理せよ

• \(s\) が与えられる。\(X\) に含まれていない最小の \(s\) の繰り返しを求めて出力し、それを \(X\) に追加する

ある文字列を何度か繰り返した文字列が \(X\) に含まれているかどうかはローリングハッシュを用いることで高速に判定することができます。それに加え、先に述べた解法同様、\(s\) ごとに「前回の続きから調べる」ことでクエリに十分高速に答えることができます。
この解法は最初に述べた解法を \(T_i\) で分類せずにやっているのとほぼ等価なので、計算量は同じ \(O(L(\log L)^2)\) になります。
\(L\) 種類程度の文字列のhashを計算することになるので、hashの衝突に注意してください。