Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Equivalent strings

    Let’s have a new definition of string equivalence (~). Two strings a and b are equivalent if they have the same length and one of the two cases holds:
    1. a is identical to b (a == b)
    1. If we split a into two strings of the same size a1 and a2, and string b into two strings of the same size b1 and b2, then:
      1. a1 is equivalent to b1, and a2 is equivalent to b2 (a1 ~ b1 and a2 ~ b2)
      2. a1 is equivalent to b2, and a2 is equivalent to b1 (a1 ~ b2 and a2 ~ b1)
    Given two strings a and b, you are asked to find out if these two strings are equivalent.

    Input

    The first line of the input contains the string a (1 ≤ |a| ≤ ).
    The second line of the input contains the string b (1 ≤ |b| ≤ ).
    Both of the lengths |a| and |b| are a power of 2.

    Output

    The program should print Yes if a is equivalent to b, and No otherwise.

    Examples

    Input
    Output
    bbcb bcbb
    Yes
    bbaa baba
    No

    Explanation

    1. bbcbbb + cb, bcbbbc + bbbb is equivalent to bb, while cb is equivalent to bc as we can split cbc + b, and bcb + c ⇒ they are equivalent.
    1. bbaabb + aa, bababa + ba ⇒ no pairs are equivalent because if we split them further, we’ll need to compare aa to any of the ba-s, and therefore, as there are no b-s in aa, the two strings will not be equivalent.
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue