On-line construction of parameterized suffix trees for large alphabets

We consider on-line construction of the suffix tree for a parameterized string, where we always have the suffix tree of the input string read so far. This situation often arises from source code management systems where, for example, a source code repository is gradually increasing in its size as users commit new codes into the repository day by day. We present an on-line algorithm which constructs a parameterized suffix tree in randomized O(n)O(n) time, where n is the length of the input string. Our algorithm is the first randomized linear time algorithm for the on-line construction problem.

Research highlights► We construct parameterized suffix trees for parameterized pattern matching problem. ► On-line construction where we always have the suffix tree of the input read so far. ► The first randomized linear time algorithm for on-line construction with integer alphabets.