codeforces 560 D. Equivalent Strings(分治)

D. Equivalent Strings

time limit per test 2 seconds

memory limit per test 256 megabytes

input standard input

output standard output

Today on a lecture about strings Gerald learned a new definition of string equivalency. Two stringsaandbof equal length are calledequivalentin one of the two cases:

They are equal.
If we split stringainto two halves of the same sizea1anda2, and stringbinto two halves of the same sizeb1andb2, then one of the following is correct:
1. a1is equivalent tob1, anda2is equivalent tob2
2. a1is equivalent tob2, anda2is equivalent tob1

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 from1to200 000and 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

优质内容筛选与推荐>>
1、自执行函数。
2、Find substring with K distinct characters
3、HTTP
4、中缀表达式转换为后缀表达式
5、内置委托func

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看