Problem E
Password Rotation
Yraglac recently found a list of compromised passwords for a major online website and would like to analyze the data to find out if any two users have similar passwords. Two passwords are considered similar if they are rotations or reverse rotations of each other. The rotations of a password are formed by repeatedly removing the first letter and appending it to the end. Reverse rotations are the rotations of the reversed password. For example, given the password ABCD:
-
Rotations are: ABCD, BCDA, CDAB, DABC
-
Reverse rotations are: DCBA, CBAD, BADC, ADCB
Can you help Yraglac?
Input
The input will contain a single line with $N$, the number of compromised passwords, where $2 \leq N \leq 10^5$. Next will follow $N$ lines with one password per line. Each password will consist only of uppercase letters and will have a length between $1$ and $5\cdot 10^5$ inclusive. The sum of lengths of all passwords will not exceed $10^6$. There may be duplicate passwords in the list. (Since a password is a rotation of itself, the output will always be “Yes” when any password appears twice.)
Output
Output “Yes” if there exists any two passwords that are rotations or reverse rotations of each other, and “No” otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 ABCD XYZ CDAB |
Yes |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 ABCD XYZ CBAD |
Yes |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 ABCD XYZ ACBD |
No |
