https://www.geeksforgeeks.org/generalized-suffix-tree-1/
There are lots of other problems where multiple strings are involved.
Lets consider two strings X and Y for which we want to build generalized suffix tree. For this we will make a new string X#Y$ where # and $ both are terminal symbols (must be unique). Then we will build suffix tree for X#Y$ which will be the generalized suffix tree for X and Y. Same logic will apply for more than two strings (i.e. concatenate all strings using unique terminal symbols and then build suffix tree for concatenated string).
Lets say X = xabxa, and Y = babxba, then
X#Y$ = xabxa#babxba$
https://www.cnblogs.com/super-zhang-828/p/5920636.html
https://github.com/illya13/suffix-tree/tree/master/src/main/java/com/blogspot/illyakeeplearning/suffixtree
https://cs.nyu.edu/courses/spring14/CSCI-UA.0480-004/Lecture20Examples/SuffixTree.java
There are lots of other problems where multiple strings are involved.
Lets consider two strings X and Y for which we want to build generalized suffix tree. For this we will make a new string X#Y$ where # and $ both are terminal symbols (must be unique). Then we will build suffix tree for X#Y$ which will be the generalized suffix tree for X and Y. Same logic will apply for more than two strings (i.e. concatenate all strings using unique terminal symbols and then build suffix tree for concatenated string).
X#Y$ = xabxa#babxba$
We can use this tree to solve some of the problems, but we can refine it a bit by removing unwanted substrings on a path label. A path label should have substring from only one input string, so if there are path labels having substrings from multiple input strings, we can keep only the initial portion corresponding to one string and remove all the later portion. For example, for path labels #babxba$, a#babxba$ and bxa#babxba$, we can remove babxba$ (belongs to 2nd input string) and then new path labels will be #, a# and bxa# respectively. With this change, above diagram will look like below:
Below implementation is built on top of original implementation. Here we are removing unwanted characters on path labels. If a path label has “#” character in it, then we are trimming all characters after the “#” in that path label.
Note: This implementation builds generalized suffix tree for only two strings X and Y which are concatenated as X#Y$
Note: This implementation builds generalized suffix tree for only two strings X and Y which are concatenated as X#Y$
Followup:
Extend above implementation for more than two strings (i.e. concatenate all strings using unique terminal symbols and then build suffix tree for concatenated string)
Extend above implementation for more than two strings (i.e. concatenate all strings using unique terminal symbols and then build suffix tree for concatenated string)
One problem with this approach is the need of unique terminal symbol for each input string. This will work for few strings but if there is too many input strings, we may not be able to find that many unique terminal symbols.
We will discuss another approach to build generalized suffix tree soon where we will need only one unique terminal symbol and that will resolve the above problem and can be used to build generalized suffix tree for any number of input strings.
We will discuss another approach to build generalized suffix tree soon where we will need only one unique terminal symbol and that will resolve the above problem and can be used to build generalized suffix tree for any number of input strings.
算法目的 GST算法的提出是为了解决最大公共子串问题，也就是在多个字符串中，找到他们共有的子串。
顺便说一句
这个问题听起来和最大公共子序列问题（LCS）有些相似，但是二者有两个不同点：
①一个是公共子串，一个是公共子序列，后者可以是不连续的；
②GST算法可以对多个字符串求公共子串，而我们一般指的LCS算法只能对两个字符串求公共子序列。
后缀树，顾名思义，是一个字符串的所有后缀构成的一棵树。那么我们为什么要把一个字符串的所有后缀，提取出来呢？
对于"p in S?"这个问题，我们假设S=rpq，这时我们看到pq是S的后缀，p为S的后缀pq的前缀。
也就是说，如果p在S中出现，那么我们一定能找到S的一个后缀，使得p是这个后缀的前缀。因此，为了判断"p in S?"这个问题，我们将S所有的后缀提取出来，与p进行比对。为了加快比对的效率，我们把所有的后缀建成一棵树。
上面我们，那么如果p in S1，p in S2，那么p是S1和S2的子串。因此，对于多个字符串S1,S2,……,Sn，建立一颗包含它们全部后缀的后缀树，那么重合的节点就是他们的公共子串了。
五、再举个例子
我们举个例子吧。对于{abcde,cdef,ccde}，首先对abcde建立后缀树，如下
然后把cdef的所有后缀加进去，得到下面的树
最后把ccde的所有后缀加进去，
这是，我们可以看到，cde就是{abcde,cdef,ccde}的最长公共子串了。
To find the longest common substring of 2 strings (
T and S), I've read that we must build a suffix tree for the string T($1)S($2), where`($1) and ($2) are special characters not part of the strings.
But the Wikipedia image for the strings 
ABAB and BABA looks like this:
Why doesn't it contain the entire string
ABAB($1)BABA($2) ? Isn't it a suffix of the concatenated string?
A generalized suffix tree is a variation on a suffix tree in which the suffixes for two (or more) distinct strings T1 and T2 are stored, not just the suffixes of one string T.
One way to build a generalized suffix tree is to start by making a suffix tree for T1$1T2$2. This resulting suffix tree will contain all the suffixes of T1 and T2, but it will also contain a lot of "spurious" suffixes that start in T1 and spread into T2. To fix this, after building the initial suffix tree, you would typically make a second pass over the tree structure and eliminate any suffixes that extend past the $1 marker. This is why, for example, the generalized suffix tree you gave above doesn't contain ABAB$1BABA$2.
As to your next question - what are the numbers in the leaves? - each leaf in a suffix tree is typically tagged with the start index of the suffix that the leaf corresponds to. In a generalized suffix tree, each leaf is tagged with two pieces of information - the start index of the suffix, and which string that suffix belongs to. The notation a:b on a leaf means "this suffix comes from string a, and it starts at index b in that string." For example, the marker 1:3 on the leftmost leaf means "this suffix comes from string 1 and it starts at position 3." You can see that this corresponds to the suffix A$1, which does indeed start at position 3 in ABAB$1, assuming 1-indexing.
TODO
http://illya-keeplearning.blogspot.com/2009/04/suffix-trees-java-ukkonens-algorithm.htmlhttps://github.com/illya13/suffix-tree/tree/master/src/main/java/com/blogspot/illyakeeplearning/suffixtree
https://cs.nyu.edu/courses/spring14/CSCI-UA.0480-004/Lecture20Examples/SuffixTree.java
