Codeforces Round #313 Equivalent Strings（递归）

D. Equivalent Strings

time limit per test

memory limit per test

input

output

a and b of equal length are calledequivalent

1. They are equal.
2. ainto two halves of the same sizea1 anda2, and stringbinto two halves of the same sizeb1 andb2, then one of the following is correct:

1. a1 is equivalent tob1, anda2 is equivalent tob2
2. a1 is equivalent tob2, anda2 is 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

1 to 200 000

Output

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

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".

aa" and "bb", that are equivalent only to themselves. That's why string "aabb" is equivalent only to itself and to string "bbaa".

解析：递归求解。

代码：

#include<cstdio>
#include<cstring>
#define maxn 200000
using namespace std;

char a[maxn+20],b[maxn+20];
int lena,lenb;

bool equal(char p[],int l1,int r1,char q[],int l2,int r2)
{
  if(r1-l1!=r2-l2)return 0;
  if(strncmp(p+l1,q+l2,r1-l1+1)==0)return 1;
  if((r1-l1+1)&1)return 0;
  
  int i,j,k1=(l1+r1)/2,k2=(l2+r2)/2;
  if(equal(p,l1,k1,q,l2,k2) && equal(p,k1+1,r1,q,k2+1,r2))return 1;
  if(equal(p,k1+1,r1,q,l2,k2) && equal(p,l1,k1,q,k2+1,r2))return 1;
  return 0; 
}

int main()
{
  int i,j,k;
  scanf("%s%s",a,b);
  lena=strlen(a),lenb=strlen(b);
  if(equal(a,0,lena-1,b,0,lenb-1))
    printf("YES\n");
  else 
    printf("NO\n");
  return 0;
}