Generalized Suffix Tree

An implementation of generalized suffix tree using Ukkonenโ€™s algorithm. In this page: The longest common substring problem How it works GST versus Dynamic programming Inspired by: Ukkonen, E. On-line construction of suffix trees. Algorithmica 14, 249โ€“260 (1995). https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf The longest common substring problem Given two or more strings, find the longest common substring of these strings. Concretely, the longest common substring of the two strings โ€œcacaocacโ€ and โ€œccaoocโ€ is โ€œcaoโ€. This seems like a simple problem, but until today, it still requires a complicated algorithm to be solved in a reasonable time....

December 23, 2020 ยท 4 min ยท Sidney Liu