On-line construction of parameterized suffix trees for large alphabets. (English) Zbl 1260.68459
Summary: 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)\) 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.
References:
| [1] | B.S. Baker, A theory of parameterized pattern matching: algorithms and applications, in: STOC ’93: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993, pp. 71-80.; B.S. Baker, A theory of parameterized pattern matching: algorithms and applications, in: STOC ’93: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993, pp. 71-80. · Zbl 1310.68098 |
| [2] | Baker, B. S., Parameterized duplication in strings: Algorithms and an application to software maintenance, SIAM J. Comput., 26, 5, 1343-1362 (1997) · Zbl 0885.68085 |
| [3] | Shibuya, T., Generalization of a suffix tree for RNA structural pattern matching, Algorithmica, 39, 1, 1-19 (2004) · Zbl 1089.68031 |
| [4] | P. Weiner, Linear pattern matching algorithms, in: SWAT ’73: Proceedings of the 14th Annual Symposium on Switching and Automata Theory, 1973, pp. 1-11.; P. Weiner, Linear pattern matching algorithms, in: SWAT ’73: Proceedings of the 14th Annual Symposium on Switching and Automata Theory, 1973, pp. 1-11. |
| [5] | McCreight, E. M., A space-economical suffix tree construction algorithm, J. ACM, 23, 2, 262-272 (1976) · Zbl 0329.68042 |
| [6] | Ukkonen, E., On-line construction of suffix trees, Algorithmica, 14, 3, 249-260 (1995) · Zbl 0831.68027 |
| [7] | Farach-Colton, M.; Ferragina, P.; Muthukrishnan, S., On the sorting-complexity of suffix tree construction, J. ACM, 47, 6, 987-1011 (2000) · Zbl 1094.68694 |
| [8] | Kosaraju, S. Rao, Faster algorithms for the construction of parameterized suffix trees, (FOCS ’95: Proceedings of the 36th Annual Symposium on Foundations of Computer Science (1995), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 631 · Zbl 0938.68918 |
| [9] | Cole, R.; Hariharan, R., Faster suffix tree construction with missing suffix links, SIAM J. Comput., 33, 1, 26-42 (2004) · Zbl 1069.68644 |
| [10] | Giegerich, R.; Kurtz, S., From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction, Algorithmica, 19, 3, 331-353 (1997) · Zbl 0895.68056 |
| [11] | Na, J. C.; Kim, N.; Sim, J. S.; Kim, D. K., Improving on-line construction of two-dimensional suffix trees for square matrices, Inform. Process. Lett., 109, 10, 504-508 (2009) · Zbl 1214.68460 |
| [12] | D.K. Kim, J.C. Na, J.S. Sim, K. Park, Linear-time construction of two-dimensional suffix trees, Algorithmica (2009), in press; published online, doi:10.1007/s00453-009-9350-z; D.K. Kim, J.C. Na, J.S. Sim, K. Park, Linear-time construction of two-dimensional suffix trees, Algorithmica (2009), in press; published online, doi:10.1007/s00453-009-9350-z · Zbl 1213.68228 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
