D. Equivalent Strings
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include <string> 7 #include 8 #include <set> 9 #include 10 #include 11 #include 12 using namespace std; 13 typedef __int64 LL; 14 const int INF = 0x4ffffff; 15 const double EXP = 1E-5; 16 const LL mod = 1e9+7; 17 const int MS= 200005; 18 19 20 bool equals(string s1,string s2) 21 { 22 int len1 = s1.size(); 23 int len2 = s2.size(); 24 if(s1 == s2) 25 return true; 26 else if(len1 != len2 || (len1&1) ==1 || (len2 &1) ==1) 27 return false; 28 else 29 { 30 // if(equals(s1.substr(0,len1/2),s2.substr(0,len1/2)) && equals(s1.substr(len1/2,len1/2),s2.substr(len1/2,len1/2))) 31 // return true; // 不把这个放后面会超时，因为前面的s1 == s2没有通过。说明相同位置上有字符不同。先交叉比较能够优化。 32 33 if(equals(s1.substr(0,len1/2),s2.substr(len1/2,len1/2)) && equals(s1.substr(len1/2,len1/2),s2.substr(0,len1/2))) 34 return true; 35 if(equals(s1.substr(0,len1/2),s2.substr(0,len1/2)) && equals(s1.substr(len1/2,len1/2),s2.substr(len1/2,len1/2))) 36 return true; 37 38 return false; 39 } 40 } 41 42 43 int main() 44 { 45 string s1,s2; 46 cin>>s1>>s2; 47 if(equals(s1,s2)) 48 printf("YES\n"); 49 else 50 printf("NO\n"); 51 return 0; 52 }
京公网安备 11010802041100号