[Codeforces][559B][560D] B. Equivalent Strings

原題：http://codeforces.com/problemset/problem/559/B
AC：http://codeforces.com/contest/559/submission/12532597

解題方向：模擬


題目大意：給你兩個等長的字串，定義兩字串$A,B$等價，是滿足下其中之一的條件：

1. $A = B$
2. 若能將A分成等長的字串$A1,A2$，也把B分成$B1,B2$，則滿足其中之一：

• $A1$等價$B1$，且$A2$等價$B2$
• $A1$等價$B2$，且$A2$等價$B1$

判定給定字串是否等價。
註 第二點的分割方法是指 $A=A1A2,B=B1B2$

解法：

感覺複雜度不大對，但是暴力做會AC，而且滿快的$(45ms)$，頗奇妙。
分析複雜度 $T(N) = 4T(\frac{N}{2})+2n$，主導者定理得到複雜度$O(N^2)$，但是大小$200000$還是過了，得找點資料研究下哪裡有問題。

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

char A[200001];
char B[200001];
int L;

bool check(const char *a,const char *b,int len)
{
    if( strncmp(a,b,len) == 0 ) return true;
    if( len%2 == 1 )return false;
    len/=2;
    return check(a,b+len,len)&&check(a+len,b,len)||
           check(a,b,len)&&check(a+len,b+len,len);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>A>>B;
    L = strlen(A);
    cout<< (check(A,B,L)?"YES":"NO") <<'\n';
}

PS. 如果設定正確的話應該會出現在FB上