Codeforces Round #313 (Div. 1) B. Equivalent Strings

Codeforces Round #313 (Div. 1)に参加しました。
AしかACせずお通夜でした。そろそろ感覚戻ってきたし良い結果も出したい…

問題

Problem - B - Codeforces

解法

２つの文字列についてある意味「ソート」のようなことをして,それぞれが一致するかどうかを判定すれば良いことがわかります。

それを素直に実装すると下のコードのようになります。これは深さがlog nになるのでcreateにかかる計算時間はです。

string A, B;
int n;

string create(string s) {
    int n = s.size();
    if (n % 2 == 1) return s;
    string a = create(s.substr(0, n/2));
    string b = create(s.substr(n/2, n/2));
    if (a > b) swap(a, b);
    return a+b;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> A;
    cin >> B;
    n = A.size();
    if (create(A) == create(B)) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}