It's possible to solve this problem in $O(n)$?

Question

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

Answer 1

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)
```