Faster Algorithms for the Construction of Parameterized Suffix Trees Preliminary Version
S. Rao Kosaraju · Foundations of Computer Science · 1995
Parameterized strings were introduced by Baker to solve the problem of identifying blocks of code that get duplicated in a large software system. Parameter symbols capture the notion of code identity while permitting renaming of variables. The code duplication problem was solved by first constructing a generalized suffix tree for the corresponding Parameterized strings. The fastest known generalized suffix tree algorithm has an O(n(lIIl+ ZoglCI)) speed., where n is the length of the input, II is the set of parameters, and C is the set of fixed symbols. Here isn algorithm that has a running time of O(n loglIIl loglCl) is constructed. The algorithm is then improved to another that has a running time of O(n(ZoglIIl + loglcl)).