問題概要

2 つの文字列 $A, B$ は、

$A = B$ である
$A$ を左右反転してできる文字列 $A'$ について、 $A' = B$ である

といういずれかの条件を満たすとき、似ているとみなす。

与えられた $N$ 個の文字列 $S_{1}, S_{2}, \dots, S_{N}$ について、似ている文字列は同一視することにすると、何種類の文字列があるか。

制約

$N \le 2 \times 10^{5}$
すべての文字列の長さの合計が $2 \times 10^{5}$ 以下

考えたこと

2 つの文字列 $A, B$ が等しいという条件を、次のように言い換えよう！　ここで、文字列 $A$ を左右反転して得られる文字列を $A'$ というようにダッシュをつけて表すことにする。

【文字列が等しい条件】

文字列 $A, B$ があるとする。

$A$ に対して、 $f(A) = \min(A, A')$ とする
$B$ に対して、 $f(B) = \min(B, B')$ とする

このとき、 $A, B$ が似ている必要十分条件は、

$f(A) = f(B)$

であることである。

たとえば、"dog" と "god" は次のようにして、似ていると判定される。

f("dog") = "dog"
f("god" ) = "dog"

であり、これらは一致するので、"dog" と "god" は似ている。

`set` で管理

このような条件の言い換えができれば、あとは簡単だ。文字列を管理する集合を用意して、集合に $f(S_{1}), f(S_{2}), \dots, f(S_{N})$ を挿入していき、集合のサイズを答えればよい。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    string S;

    set<string> se;
    for (int i = 0; i < N; i++) {
        cin >> S;
        auto T = S;
        reverse(T.begin(), T.end());
        se.insert(min(S, T));
    }
    cout << se.size() << endl;
}