公式

Ex - snukesnuke 解説 by en_translator

We denote the length of a string \(T\) by \(|T|\). Let \(L\) be \(\sum |S_i|\).

For each string \(S_i\), find the minimum \(p_i\) that is a period of \(S_i\) and a divisor of \(|S_i|\), and let \(T_i\) be the length-\(p_i\) prefix of \(S_i\).
For example, \(S_i=\) abcabcabc becomes \(T_i=\) abc, and \(S_i=\) ababa remains \(T_i=\) ababa.
Finding these \(p_i\) and \(T_i\) can be done in an \(O(|S_i|)\) time with the Z-algorithm.

Two people with different \(T_i\) can never have the same candidates of nicknames in common, so we can group them by \(T_i\) and consider each group independently.

Suppose that we have grouped them according to \(T_i\); in other words, suppose that \(T_i\) are equal for all \(i\). Then, two nicknames coincides if and only if they have the same lengths, so it is sufficient to maintain a set of lengths of the nicknames given so far, and solve the following problem on it:

Process the following type of queries fast against an initially empty set \(X\) of positive integers.

  • Given \(n\), find the minimum multiple of \(n\) not contained in \(X\), print it, and insert it to \(X\).

Such queries can be answered by memorizing the answer to the previous query for each \(n\), and searching for the answer to the next query successively from the memorized value, in a total of \(O(L (\log L)^2)\) time.

We can show that the resulting nicknames’ lengths are at most \(L\). Thus, \(\max X\leq L\), so “advancing to check whether \(m+n\in X\) because \(m\in X\)” happens at most \(O(L/n)\). Thus, this process occurs \(O(L\log L)\) time; together with the cost of the set, it costs a total of \(O(L(\log L)^2)\) time.

Therefore, the problem has been solved in a total of \(O(L(\log L)^2)\) time.

Writer’s solution (C++)

Solution using rolling hash

A naive formalization of the original problem is as follows.

Process the following type of queries fast against an initially empty set \(X\) of strings.

  • Give \(s\), find the minimum repetition of \(s\) not contained in \(X\), print it, and insert it to \(X\).

One can determine fast if a repetition of a string is contained in \(X\) based on rolling hash. Additionally, we can again exploit the “resuming from the last answer” trick to answer queries fast enough.
This solution is equivalent to the original solution except that we do not group by \(T_i\), so the complexity is still \(O(L(\log L)^2)\).
Beware of hash collisions, as we need to compute hashes of about \(L\) different strings.

投稿日時:
最終更新: