{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T16:11:23Z","timestamp":1770480683766,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540560241","type":"print"},{"value":"9783540473572","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-56024-6_19","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:53:21Z","timestamp":1330253601000},"page":"230-243","source":"Crossref","is-referenced-by-count":41,"title":["Color Set Size problem with applications to string matching"],"prefix":"10.1007","author":[{"given":"Lucas","family":"Chi","sequence":"first","affiliation":[]},{"given":"Kwong","family":"Hui","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-3-642-82456-2_6","volume-title":"Combinatorial Algorithms on Words, NATO ASI Series, Series F: Computer and System Sciences, Vol. 12","author":"A. Apostolico","year":"1985","unstructured":"A. Apostolico. The myriad virtues of subword trees. In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, NATO ASI Series, Series F: Computer and System Sciences, Vol. 12, pages 85\u201396, Springer-Verlag, Berlin, 1985."},{"key":"19_CR2","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/BF01762122","volume":"3","author":"A. Apostolico","year":"1988","unstructured":"A. Apostolico, C. Iliopoulos, G. M. Landau, B. Schieber, and U. Vishkin. Parallel construction of a suffix tree with applications. Algorithmica, 3:347\u2013365, 1988.","journal-title":"Algorithmica"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di. An O(n log n) sorting network. In Proc. of the 15th ACM Symposium on Theory of Computing, pages 1\u20139, 1983.","DOI":"10.1145\/800061.808726"},{"key":"19_CR4","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1137\/0149012","volume":"49","author":"S. Altschul","year":"1989","unstructured":"S. Altschul and D. Lipman. Trees, stars, and multiple biological sequence alignment. SIAM Journal on Applied Math, 49:197\u2013209, 1989.","journal-title":"SIAM Journal on Applied Math"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"R. Cole. Parallel merge sort. In Proc. 27nd Annual Symposium on the Foundation of Computer Science, pages 511\u2013516, 1986.","DOI":"10.1109\/SFCS.1986.41"},{"key":"19_CR6","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1137\/0148063","volume":"48","author":"H. Carrillo","year":"1988","unstructured":"H. Carrillo and D. Lipman. The multiple sequence alignment problem in biology. SIAM Journal on Applied Math, 48:1073\u20131082, 1988.","journal-title":"SIAM Journal on Applied Math"},{"key":"19_CR7","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/BF01762121","volume":"3","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin. The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time. Algorithmica, 3:329\u2013346, 1988.","journal-title":"Algorithmica"},{"key":"19_CR8","volume-title":"Technical Report CSE-91-4, Computer Science","author":"D. Gusfield","year":"1991","unstructured":"D. Gusfield. Efficient methods for multiple sequence alignment with guaranteed error bounds. Technical Report CSE-91-4, Computer Science, U. C. Davis, 1991."},{"key":"19_CR9","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0890-5401(87)90062-9","volume":"75","author":"T. Hagerup","year":"1987","unstructured":"T. Hagerup. Towards optimal parallel bucket sorting. Information and Computation, 75:39\u201351, 1987.","journal-title":"Information and Computation"},{"key":"19_CR10","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1109\/TC.1985.6312202","volume":"C-34","author":"C. Kruskal","year":"1985","unstructured":"C. Kruskal, L. Rudolph, and M. Snir. The power of parallel prefix. IEEE Trans. Comput. C-34:965\u2013968, 1985.","journal-title":"IEEE Trans. Comput."},{"key":"19_CR11","unstructured":"R. Lo. personal communications. 1991."},{"key":"19_CR12","first-page":"831","volume":"27","author":"L. Ladner","year":"1980","unstructured":"L. Ladner and M. Fischer. Parallel prefix computation. J.A.C.M., 27:831\u2013838, 1980.","journal-title":"J.A.C.M."},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"G. M. Landau and U. Vishkin. Introducing efficient parallelism into approximate string matching and a new serial algorithm. In Proc. of the 18th ACM Symposium on Theory of Computing, pages 220\u2013230, 1986.","DOI":"10.1145\/12130.12152"},{"issue":"13","key":"19_CR14","doi-asserted-by":"crossref","first-page":"4629","DOI":"10.1093\/nar\/11.13.4629","volume":"11","author":"H. M. Martinez","year":"1983","unstructured":"H. M. Martinez. An efficient method for finding repeats in molecular sequences. Nucleic Acids Research, 11(13):4629\u20134634, 1983.","journal-title":"Nucleic Acids Research"},{"issue":"2","key":"19_CR15","first-page":"262","volume":"23","author":"E. M. McCreight","year":"1976","unstructured":"E. M. McCreight. A space-economical suffix tree construction algorithm. J.A.C.M., 23(2):262\u2013272, 1976.","journal-title":"J.A.C.M."},{"key":"19_CR16","unstructured":"Y. Maon, B. Schieber, and U. Vishkin. Open ear decomposition and s-t numbering in graphs. Theoretical Computer Science, 1987."},{"key":"19_CR17","unstructured":"V. R. Pratt. Improvements and applications for the weiner repetition finder. 1975. unpublished manuscript."},{"key":"19_CR18","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1137\/0218041","volume":"18","author":"S. Rajasekaran","year":"1989","unstructured":"S. Rajasekaran and J. H. Reif. Optimal and sublogarithmic time randomized parallel sorting algorithms. SIAM Journal on Computing, 18:594\u2013607, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"19_CR19","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"B. Schieber and U. Vishkin. On finding lowest common ancestors: simplification and parallelization. SIAM Journal on Computing, 17:1253\u20131262, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"19_CR20","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan and U. Vishkin. An efficient parallel biconnectivity algorithm. SIAM Journal on Computing, 14:862\u2013874, 1985.","journal-title":"SIAM Journal on Computing"},{"key":"19_CR21","first-page":"235","volume":"20","author":"U. Vishkin","year":"1985","unstructured":"U. Vishkin. On efficient parallel strong orientation. I.P.L., 20:235\u2013240, 1985.","journal-title":"I.P.L."},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"P. Weiner. Linear pattern matching algorithms. In Proc. 14th IEEE Symp. on Switching and Automata Theory, pages 1\u201311, 1973.","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56024-6_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:02:41Z","timestamp":1605646961000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56024-6_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540560241","9783540473572"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-56024-6_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]}}}