1848. Grouping Words That Are Rotations of One Another
m words are given. Two words belong to the same group when one is a rotation of
the other, where rotating by k means moving the first k characters to the
back. Print how many groups there are.
Words of different lengths are never rotations of each other. Identical words are, by a rotation of 0.
abc, bca, cab, acb -> 2 the first three are one group
aaa, aaa, aa -> 2 the third has a different LENGTH
ab, ba -> 1
abcd, dcba, bcda, cdab -> 2 dcba is reversed, not rotated
abab, baba, abba -> 2
## What most people try first
Compare every pair of words to see whether one is a rotation of the other, which
problem 1813 does in O(L) per pair. That is m^2 / 2 pairs, and at
m = 100000 it is 5 * 10^9 pair tests before the cost of each one. The method
below is about 1.4 * 10^8 and never compares two words directly.
## Give every word a canonical name
Being a rotation of is an equivalence: every word is a rotation of itself, the relation is symmetric, and rotating twice is rotating once by the sum. So the words fall into groups, and all that is needed is a name that is the same for every word in a group and different across groups.
The SMALLEST rotation is such a name. Two words are rotations of each other exactly when they have the same smallest rotation, because the set of rotations is the same set for both, and the smallest element of a set is determined by the set.
for each word w:
canonical[w] = the smallest rotation of w, from problem 1844
answer = the number of distinct canonical names
Words of different lengths get names of different lengths, so they can never collide, and no separate length check is needed.
## Why not just count distinct sorted letter multisets
Because that is a different relation. abcd and dcba have the same letters
and are not rotations, and the fourth example is in the tests for that reason. A
letter count is a necessary condition, never a sufficient one.
## Cost
Each word of length L costs O(L log^2 L) for the suffix array over its
doubled copy. With the total length capped at 200000 that is at most about
1.4 * 10^8 operations for all the words together, reached when one word takes
the whole budget, plus O(total length) characters for storing and comparing
the names.
Constraints - `1 ≤ m ≤ 100000` - `1 ≤ length of each word` - the total length of all the words is at most `200000` - every word is lowercase English letters - words may repeat, and repeated words share a group - a rotation is not an occurrence, so overlap does not arise, and a count of groups is wanted rather than the groups themselves
Input
The first line contains the integer m.
Each of the next m lines contains one word of lowercase English letters.
Output
Print one integer on its own line: how many groups the words fall into, where two words share a group exactly when one can be turned into the other by moving some number of characters from its front to its back.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.