Suffix tree of two strings
Given two strings, s and t, your task is to construct a compressed suffix tree that includes all suffixes of both strings.
The goal is to create a tree with the minimum number of vertices.
Input
The first line contains the string s (1 ≤ |s| ≤ 10^4), ending with the character "$". All other characters are lowercase Latin letters. The second line contains the string t (1 ≤ |t| ≤ 10^4), ending with the character "#". All other characters are lowercase Latin letters.
Output
Number the vertices of the tree from 0 to n-1 using a depth-first search, ordering subtrees based on the lexicographical order of the outgoing edges from each vertex. Use the ASCII values of characters to determine this order.
First, output an integer n, which is the total number of vertices in the tree. Then, for the next n-1 lines, provide the description of each tree vertex, excluding the root, in ascending order of their numbers.
The description for a vertex v includes four integers: p, w, lf, rg. Here, p (0 ≤ p < n, p ≠ v) is the parent vertex number, w (0 ≤ w ≤ 1) indicates which string determines the substring on the edge. If w=0, the edge from p to v contains the substring s[lf...rg-1] (0 ≤ lf < rg ≤ |s|). If w=1, the edge contains the substring t[lf...rg-1] (0 ≤ lf < rg ≤ |t|).