7 / 8 Wavelet Trees & Succinct Text Machinery

The Minus One Root

An Eertree has two roots, one of length 00 and one of length −1-1. What is the −1-1 root for?

A

It is a sentinel whose transitions all fail. Extending a length −1-1 palindrome by one character on each side is undefined, so the fail-pointer walk terminates with no length check in the code.

B

It is the virtual parent of the odd-length palindromes. Extending a length −1-1 palindrome by one character on each side gives a single character, so odd palindromes get a base case with no special case in the code.

C

It is the node for the empty string. Extending a length −1-1 palindrome by one character on each side gives a single character, so the fail links form one tree instead of a forest with no special case in the code.

D

It is the virtual parent of the even-length palindromes. Extending a length −1-1 palindrome by one character on each side gives two characters, so even palindromes get a base case with no special case in the code.