CFR 559 B. Equivalent Strings ( D&C )

Problem - 559B - Codeforces

題意：
對字串定義一個比較函數：
若 A == B 則 f( A, B ) = 1
若他們的長度相同，且長度為偶數，那麼分成兩半 A[ 0 .. size / 2 ), A[ size / 2, size ) 後，左右兩半對調，若對調後的 f( A', B ) = 1，那麼 f( A, B ) = 1。

資料規模：
字串長度 1 ≤ | str | ≤ 2e5
時限 2000 ms
記憶體 256 MB

解法：
注意到比較函數為 f( A, B ) 的所有 A 和 B 是一個可相互到達的，可以看成一個群，所以只要能用群中某一個來代表，就能快速比較。把兩個字串屬於的群裡字典序最小的算出來比較是否相等即可。

時間 / 空間複雜度：
O( N lg N )

string A, B;

void init(){
    cin >> A >> B;
}

string lex_first( const string &s ){
    if( ( int ) s.size() & 1 )
        return s;
    string a = lex_first( s.substr( 0, s.size() / 2 ) );
    string b = lex_first( s.substr( s.size() / 2 ) );
    return a < b ? a + b : b + a;
}

void preprocess(){
    A = lex_first( A );
    B = lex_first( B );
}

void solve(){
    string ans[] = { "NO", "YES" };
    cout << ans[ A == B ] << endl;
}