思维,递归
题意:
Cgg特别喜欢收集特别的字符串。这天,lfgg给了cgg两个字符串,字符串A,字符串B,声称这是一对神奇的字符串,他们满足如下两个条件的其中之一:
1、 A与B相等。
2、 如果我们把字符串A分成两个长度相等的字符串A1,A2,并将字符串B分成两个长度相等的字符串B1,B2 然后他们满足以下的其中一项条件:
(1) A1与B1是一对神奇的字符串,并且A2与B2是一对神奇的字符串。
(2) A2与B1是一对神奇的字符串,并且A1与B2是一对神奇的字符串。
Lfgg确信他找到了一对神奇字符串,cgg却并不相信。
希望你能帮帮cgg判断,这对字符串是否是一对神奇字符串。
Input
一共两行,一对字符串。
字符串长度为1到200000且仅包含小写英文字母,保证两个字符串长度一致。
Output
如果这是一对神奇字符串,输出“YES”(不含引号)。否则,输出“NO”(不含引号)。
Examples
Input
aaba
abaa
Output
YES
Input
aabb
abab
Output
NO
Note
在第一组样例中,将第一个字符串拆成aa,ba,将第二个字符串拆成ab,aa,显然aa与aa是一对神奇字符串,ba与ab是一对神奇字符串,因为ba与ab可以被拆分成b,a与a,b。
分析
我们的第一反应肯定是递归搜索,直接暴力做了他!
但是,真的能行吗?
代码如下:
#include<iostream> #include<string> #include<cstring> using namespace std; string s1; string s2; bool solve(int l1,int r1,int l2,int r2) { if ( (r1 - l1) == 0)return true; int i; for (i = 0;i < r1 - l1;i++) if (s1[i + l1] != s2[i + l2])break; if (i == r1 - l1)return true; if ((r1 - l1) & 1)return false; int mid1 = (l1 + r1) >> 1; int mid2 = (l2 + r2) >> 1; if (solve(l1, mid1, l2, mid2) && solve(mid1, r1, mid2, r2))return true; if (solve(l1, mid1, mid2, r2) && solve(mid1, r1, l2, mid2))return true; return false; } int main() { ios::sync_with_stdio(0); cin >> s1 >> s2; if (solve(0,s1.size(),0,s2.size()))cout << "YES\n"; else cout << "NO\n"; }
其实当我们看到
if (solve(l1, mid1, l2, mid2) && solve(mid1, r1, mid2, r2))return true; if (solve(l1, mid1, mid2, r2) && solve(mid1, r1, l2, mid2))return true;
时就已经感到有点不妙了。。
每一次处理下去,所需处理的数据量都需要加倍!!!!!!
(可以画个递归树看看)
这会导致我们的数据处理时间复杂度向O(n^2)方向靠拢!!!!
所以这是不行的!!!!!!
下面是正确的思路
我们再次回顾一下我们需要解决的问题:
我们需要知道字符串s1与字符串s2是否等价!
等价有一些十分重要的性质:传递性,反身性,等价性
这里我们利用传递性!
如果字符串s1等价于字符串s3且字符串s2等价于字符串s3那么字符串s1等价于字符串s3
按照这个性质我们可以确定,对于等价的s1与s2,他们一定身处在同一个等价字符串集合中!!!!
那么我们求等价于字符串s1的最小的字符串ss1,求等价与s2的最小字符串ss2
我们看一看ss1是否相等于ss2,就ok了!!!!!
下面给出代码,注意细节
#include<iostream> #include<string> #include<cstring> using namespace std; string s1; string s2; bool solve(int l1,int r1,int l2,int r2) { if ( (r1 - l1) == 0)return true; int i; for (i = 0;i < r1 - l1;i++) if (s1[i + l1] != s2[i + l2])break; if (i == r1 - l1)return true; if ((r1 - l1) & 1)return false; int mid1 = (l1 + r1) >> 1; int mid2 = (l2 + r2) >> 1; if (solve(l1, mid1, l2, mid2) && solve(mid1, r1, mid2, r2))return true; if (solve(l1, mid1, mid2, r2) && solve(mid1, r1, l2, mid2))return true; return false; } int main() { ios::sync_with_stdio(0); cin >> s1 >> s2; if (solve(0,s1.size(),0,s2.size()))cout << "YES\n"; else cout << "NO\n"; }