[R22E]相似对数 - 代码源竞赛平台

时空限制

1S/512M

题目描述

定义两个字符串 $s_i$ 和 $s_j$ 相似，当且仅当 $s_i$ 可以通过任意次循环移位（包括零次）后与 $s_j$ 相等。

循环移位指将字符串开头的若干个字符移动到字符串尾部。例如，字符串 abcd 经过一次循环移位可以得到 bcda，再移位得到 cdab，以此类推。

给定 $n$ 个字符串，请计算有多少个无序对 $(i, j)$（其中 $i < j$）满足 $s_i$ 和 $s_j$ 相似。

格式

输入格式

第一行包含一个整数 $n$。

接下来 $n$ 行，每行一个字符串 $s_i$，字符串由小写字母组成。

输出格式

输出一个整数，表示满足条件的无序对的数量。

样例

样例输入 #1

3
abc
bca
vc

样例输出 #1

1

样例解释 #1

可以发现 $s_1$ 与 $s_2$ 相似，故 $(1,2)$ 满足条件。

且 $(1,3),(2,3)$ 均不满足题目中的条件，故满足条件的无序对的数量是 $1$。

数据规模

对于 $30\%$ 的数据，$1 \leq n \leq 1000$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，字符串仅由小写字母组成，且长度均不超过 $5$。