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)$?

  • 4
    $\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 '21 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 '21 at 10:39

This problem can be formulated as a rooted tree isomorphism problem. Let $k$ be the maximum integer such that $2^k$ divides $n$. Then, each input string represents a full binary tree of height $k + 1$. Each leaf $i$ has the label $s[i n/2^k, (i+1)n/2^k-1]$ while internal nodes are unlabeled. Two trees are isomorphic if and only if the strings are dual.

Assume the alphabets of the strings can be represented as an integer less than $O(n^c)$ for constant $c$. Then, the bottom-up tree canonization algorithm of Aho-Hopcroft-Ullman solves the tree isomorphism problem in $\Theta(n)$ time in the word-RAM model. Explanation of the algorithm can be found in e.g. this lecture slide https://www.cs.uu.nl/docs/vakken/an/an-isomorphism-2016.pdf.

Because the trees are binary in this case, the algorithm can be simplified. Also, the algorithm can be implemented without integer sorting algorithms if a hash table is used, though the runtime bound becomes an expected time theoretically. Pseudocode is:

labels = {} # a hash table

def canonicalize(s, depth, i):
  if depth == k:
    return s[i] # Assumes n == 2^k for simplicity

  l = canonicalize(s, depth + 1, i * 2)
  r = canonicalize(s, depth + 1, i * 2 + 1)
  if l > r:
      l, r = r, l

  if (l, r) not in labels:
    labels[(l, r)] = labels.len()

  return labels[(l, r)]

label1 = canonicalize(s_1, 0, 0)
label2 = canonicalize(s_2, 0, 0)
print(label1 == label2)

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.