codeforces 560 D. Equivalent Strings(分治)

Today on a lecture about strings Gerald learned a new definition of string equivalency. Two strings a and b of equal length are called equivalent in one of the two cases:

They are equal.
If we split string a into two halves of the same size a1 and a2, and string b into two halves of the same size b1and b2, then one of the following is correct:
1. a1 is equivalent to b1, and a2 is equivalent to b2
2. a1 is equivalent to b2, and a2 is equivalent to b1

As a home task, the teacher gave two strings to his students and asked to determine if they are equivalent.

Gerald has already completed this home task. Now it's your turn!

Input

The first two lines of the input contain two strings given by the teacher. Each of them has the length from 1 to200 000 and consists of lowercase English letters. The strings have the same length.

Output

Print "YES" (without the quotes), if these two strings are equivalent, and "NO" (without the quotes) otherwise.

Sample test(s)

input

aaba
abaa

output

YES

input

aabb
abab

output

NO

Note

In the first sample you should split the first string into strings "aa" and "ba", the second one — into strings "ab" and "aa". "aa" is equivalent to "aa"; "ab" is equivalent to "ba" as "ab" = "a" + "b", "ba" = "b" + "a".

In the second sample the first string can be splitted into strings "aa" and "bb", that are equivalent only to themselves. That's why string "aabb" is equivalent only to itself and to string "bbaa".

问两个长度相同的字符串是否等价．

相等的条件是，两个字符串相等，或者两个偶数长度（因为要分成长度相同的两段，所以一定是偶数长度才可分）字符串平均分成两部分，每部分对应相等(不考虑顺序)

一开始有一点没想清楚.

如果字符串a分成相等长度的两部分a1,a2,字符串b分成相等的两部分b1,b2

我错误得以为,如果a1和a2等价&&b1和b2等价,那么a 和 b 就相等了(a和b一定等价,但不一定相等),于是只判断了 equal(a1,b2)&&equal(a2,b1)

wa了一次.

 1 /*************************************************************************
 2     > File Name: code/cf/#313/D.cpp
 3     > Author: 111qqz
 4     > Email: rkz2013@126.com 
 5     > Created Time: 2015年08月17日 星期一 08时42分25秒
 6  ************************************************************************/
 7 
 8 #include<iostream>
 9 #include<iomanip>
10 #include<cstdio>
11 #include<algorithm>
12 #include<cmath>
13 #include<cstring>
14 #include<string>
15 #include<map>
16 #include<set>
17 #include<queue>
18 #include<vector>
19 #include<stack>
20 #define y0 abc111qqz
21 #define y1 hust111qqz
22 #define yn hez111qqz
23 #define j1 cute111qqz
24 #define tm crazy111qqz
25 #define lr dying111qqz
26 using namespace std;
27 #define REP(i, n) for (int i=0;i<int(n);++i)  
28 typedef long long LL;
29 typedef unsigned long long ULL;
30 const int inf = 0x7fffffff;
31 const int N=2E5+7;
32 string a,b;
33 int len;
34 
35 bool equal( string x,string y,int len)
36 {
37   //  cout<<"x:"<<x<<" y:"<<y<<" len:"<<len<<endl;
38     if (x==y) return true;
39     string x1,x2,y1,y2;
40     x1 = x.substr(0,len/2);
41     x2 = x.substr(len/2,len);
42     y1 = y.substr(0,len/2);
43     y2 = y.substr(len/2,len);
44     if (len%2==0&&equal(x1,y2,len/2)&&equal(x2,y1,len/2))
45     {
46     return true;
47     }
48     if (len%2==0&&equal(x1,y1,len/2)&&equal(x2,y2,len/2))
49     {
50     return true;
51     }
52     return false;
53 }
54 int main()
55 {
56     cin>>a;
57     cin>>b;
58     len = a.length();
59     if (equal(a,b,len))
60     {
61     puts("YES");
62     }
63     else
64     {
65     puts("NO");
66     }
67       
68     return 0;
69 }

View Code

codeforces 560 D. Equivalent Strings(分治)

相关推荐