Reversible

题目描述

有 $N$ 根棒子，棒子上分别卡着若干个球。每个球上都写着一个小写英文字母。 对于每个 $i = 1, 2, \ldots, N$，第 $i$ 根棒子上球上写的字母用字符串 $S_i$ 表示。 具体来说，第 $i$ 根棒子上卡着的球的数量就是字符串 $S_i$ 的长度 $|S_i|$，并且 $S_i$ 是从棒子的一端开始的球上字母的序列。 当从某一端开始的球上字母序列相等时，两根棒子被认为是相同的。 更形式地，对于 $1$ 到 $N$ 之间的整数 $i$ 和 $j$，当且仅当 $S_i$ 等于 $S_j$ 或其反转时，第 $i$ 根和第 $j$ 根棒子被认为是相同的。 输出 $N$ 根棒子中不同棒子的数量。

输入格式

输入由标准输入提供，格式如下： $N$ $S_1$ $S_2$ $\vdots$ $S_N$

输出格式

输出答案。

6
a
abc
de
cba
de
abc

3

提示

$N$ 是一个整数。 $2 \leq N \leq 2 \times 10^5$ $S_i$ 是由小写英文字母组成的字符串。 $|S_i| \geq 1$ $\sum_{i = 1}^N |S_i| \leq 2 \times 10^5$$S_2$ = $abc$ 等于 $S_4$ = $cba$ 的反转，因此第二根和第四根棒子被认为是相同的。 $S_2$ = $abc$ 等于 $S_6$ = $abc$，因此第二根和第六根棒子被认为是相同的。 $S_3$ = $de$ 等于 $S_5$ = $de$，因此第三根和第五根棒子被认为是相同的。

因此，在六根棒子中有三种不同的棒子：第一根、第二根（与第四根和第六根相同）和第三根（与第五根相同）。

标签: AtCoder|abc310C

来源

AtCoder|abc310C