A funny way to construct suffix tree and do other things

Outline

• Problem
• Algorithm
• Complexity Analysis
• Code
• Example Problems
• Problem 1

Hello, in this blog I'll share a funny way to construct a suffix tree in $O(n{\log }^{2}n)$ time, for a given string $S$ of length $n$. I am going to call the underlying idea the "Leader Split Trick". It can probably be used to solve other problems too.

Problem

A suffix tree of a string $S$ is a radix tree constructed from all the suffixes of $S$. It's easy to see that it has $O(n)$ nodes. It can be constructed in $O(n)$ using this.

I am going to share a simple and practically useless way of building it in a worse time complexity, $O(n{\log }^{2}n)$.

Algorithm

Initially, we start with an empty tree (with a virtual root node), and a set $G$ of all suffixes from $1$ to $n$, these suffixes will be stored in the form of their starting index.

It's easy to see that the paths from the root node to $l_u\mathrm{\forall }(u\in G)$ will share some common prefix till an internal node $s_G$, after which these paths will split apart along some downward edges of the internal node. Let's define $d_G$ to be the longest common prefix across the paths $(\text{root},l_u)\mathrm{\forall }u\in G$.

Our algorithm will essentially do the following:

1. Find $d_G$.
2. Split apart $G$ into disjoint subsets $G^{\prime }$ (each subset $G^{\prime }$ will have suffixes whose leaves lie in the subtree of a unique child node of $s_G$).
3. Solve the problem recursively for each subset, and add an edge in the suffix tree from $s_G$ to $s_{G^{\prime }}$ for every $G^{\prime }$.

Now, we define a recursive function $f(G,L,\text{dep},\text{dis})$.

In each call, $f(G,L,\text{dep},\text{dis})$, we do the following:

1. If the "Leader" element $L$ is undefined:
   1. Set $L$ to a random element of $G$.
   2. For every suffix $i\in G$, find $\text{dis[i]}$, the longest common prefix of the suffixes $i$ and $L$. This can be done in $O(|G|\cdot \log n)$ using binary search + hashing. We store $\text{dis}$ in a sorted manner.
2. Let $m$ be the minimum value in $\text{dis[]}$. It's easy to see that the internal node created from splitting $G$ will occur at depth $\text{dep}+m$. We create $s_G$, and add an edge corresponding to the substring $S[L+dep+1,L+\text{dep}+m]$ from $s_{G_p}$ to $s_G$.
3. Now, we delete all suffixes $i\in G:\text{dis[i]}=m$, from $G$ (and their corresponding elements from $\text{dis}$), and group them into disjoint subsets based on the character $S_{i+\text{dep}+m+1}$ for suffix $i$ (basically the next character after the internal node).
4. We call $f(G^{\prime },\text{null},\text{dep}+m,\text{null})$ for every newly created subset $G^{\prime }$, and also call $f(G,L,\text{dep + m},\text{dis})$ for the modified subset $G$.

Note: There might be some off-by-one errors.

Complexity Analysis

Consider the following problem:

We have $n$ singleton sets, and are given some set merge operations. When merging sets $A$ and $B$, we merge $B$ to $A$ with probability $\frac{|A|}{|A|+|B|}$ and $A$ to $B$ with the probability $\frac{|B|}{|A|+|B|}$.

The above problem is computationally equivalent to Randomized Quicksort, which has an expected time complexity of $O(n\log n)$.

It's not difficult to see that our split operations are simply the operations that will occur in the above problem in a reversed manner (Formally, we can define a bijective relationship between the two sets of operations, such that related sets of operations will occur with the same probability) . Therefore, the time taken by all the split operations is $O(n\log n)$.

However, every time we perform a split operation (merge in reverse), we also compute $\text{dis}$ for the child set $C$ (which gets merged into the parent set), and that takes $O(|C|\log n)$ time. Thus, our entire algorithm has an expected time complexity of $O(n{\log }^{2}n)$.

Code

My implementation can be found here.

Example Problems

Problem 1

You are given a tree on $n$ nodes. You also have a set containing all nodes, $\{1,2,\dots ,n\}$. You have to process the following queries online:

1. "$1mx{v}_1{v}_2\dots v_x$" : Remove the nodes $v_1,v_2\dots ,v_x$ from the set $S$ whose maximum element is $m$, and create a new set with these elements (it is guaranteed that there exists some set with maximum element $m$ and $v_i\in S\mathrm{\forall }i$).
2. "$2m$" : Let the set whose maximum element is $m$ be $S$. Find some node $x\in S\mid \underset{y\in S}{max}\text{dis}(x,y)=\underset{u,v\in S}{max}\text{dis}(u,v)$.