Mathison and the Palindromic Editor

The problem can be solved by using hashing and a binary balanced search tree (a treap, for example).

We store, in every node, the hash-code and the reverse-hash-code of the substring that is contained by that node.

All operations are standard for a treap and can be performed by either traversing the tree or join/split.