Suppose given two strings $s_1$ and $s_2$ each of length $n$.

We consider $s_1$ and $s_2$ as dual, if one of the following conditions satisfied:

  1. Strings are equal.

  2. Else, if $n$ is even then:

    Divide $s_1$ into two equal partitions $a_1,a_2$, also divide $s_2$ into $b_1,b_2$ then:

    • $a_1$ with $b_1$ and $a_2$ with $b_2$ are dual.
    • Or $a_1$ with $b_2$ and $a_2$ with $b_1$ are dual.

The description above implies a recursive algorithm in $O(n\log n)$. But my question is that, is it possible to solve the problem in $O(n)$?

  • 3
    $\begingroup$ "Divide $s_1$ into two equal partition $a_1$, $a_2$" - does it mean that the length of $s_1$ is even and $a_1$ is the first half of $s_1$ and $a_2$ is the second half of $s_1$? How can it be solved in $O(n \log n)$? I see $O(n^2)$ algorithm. where running time is given by recurrence $T(n) = 4 T(\frac n2) + O(1)$. $\endgroup$
    – Dmitry
    Nov 17 at 9:22
  • 1
    $\begingroup$ You can probably solve it in $O(n)$ by using hashes: for string $s$, which consist of two parts $\alpha_1$ and $\alpha_2$, you can recursively compute $h(s) = h'(h(\alpha_1), h(\alpha_2))$, where $h'$ is some symmetric hash-function. If you properly select $h'$, it should be correct with high probability (it can only result if false-positive, and you can always check it). $\endgroup$
    – Dmitry
    Nov 17 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.