{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:11:37Z","timestamp":1725484297482},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438625"},{"type":"electronic","value":"9783540454526"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45452-7_14","type":"book-chapter","created":{"date-parts":[[2007,5,15]],"date-time":"2007-05-15T21:55:29Z","timestamp":1179266129000},"page":"153-167","source":"Crossref","is-referenced-by-count":5,"title":["The Minimum DAWG for All Suffixes of a String and Its Applications"],"prefix":"10.1007","author":[{"given":"Shunsuke","family":"Inenaga","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ayumi","family":"Shinohara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiromasa","family":"Hoshino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Setsuo","family":"Arikawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,21]]},"reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D. Angluin","year":"1980","unstructured":"D. Angluin. Finding patterns common to a set of strings. J. Comput. Sys. Sci., 21:46\u201362, 1980.","journal-title":"J. Comput. Sys. Sci."},{"issue":"2","key":"14_CR2","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0304-3975(91)90358-9","volume":"78","author":"R. A. Baeza-Yates","year":"1991","unstructured":"R. A. Baeza-Yates. Searching subsequences (note). Theoretical Computer Science, 78(2):363\u2013376, Jan. 1991.","journal-title":"Theoretical Computer Science"},{"key":"14_CR3","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(85)90157-4","volume":"40","author":"A. Blumer","year":"1985","unstructured":"A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen, and J. Seiferas. The smallest automaton recognizing the subwords of a text. Theoretical Computer Science, 40:31\u201355, 1985.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"14_CR4","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1145\/28869.28873","volume":"34","author":"A. Blumer","year":"1987","unstructured":"A. Blumer, J. Blumer, D. Haussler, R. McConnell, and A. Ehrenfeucht. Complete inverted files for efficient text retrieval and analysis. J. ACM, 34(3):578\u2013595, 1987.","journal-title":"J. ACM"},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0304-3975(86)90041-1","volume":"45","author":"M. Crochemore","year":"1986","unstructured":"M. Crochemore. Transducers and repetitions. Theoretical Computer Science, 45:63\u201386, 1986.","journal-title":"Theoretical Computer Science"},{"key":"14_CR6","unstructured":"M. Crochemore and Z. Tron\u00ed\u010dek. Directed acyclic subsequence graph for multiple texts. Technical Report IGM-99-13, Institut Gaspard-Monge, June 1999."},{"key":"14_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1007\/3-540-63246-8_12","volume-title":"Structures in Logic and Computer Science","author":"M. Crochemore","year":"1997","unstructured":"M. Crochemore and R. V\u00e9rin. On compact directed acyclic word graphs. In J. Mycielski, G. Rozenberg, and A. Salomaa, editors, Structures in Logic and Computer Science, volume 1261 of LNCS, pages 192\u2013211. Springer-Verlag, 1997."},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"R. Grossi and J. S. Vitter. Compressed suffix arrays and suffix trees with applications to text indexing and string matching. In Proc. of 32nd ACM Symposium on Theory of Computing (STOC\u201900), pages 397\u2013406, 2000.","DOI":"10.1145\/335305.335351"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"M. Hirao, H. Hoshino, A. Shinohara, M. Takeda, and S. Arikawa. A practical algorithm to find the best subsequence patterns. In S. Arikawa and S. Morishita, editors, Proc. The Third International Conference on Discovery Science, volume 1967 of LNAI, pages 141\u2013154. Springer-Verlag, 2000.","DOI":"10.1007\/3-540-44418-1_12"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"M. Hirao, S. Inenaga, A. Shinohara, M. Takeda, and S. Arikawa. A practical algorithm to find the best episode patterns. In K. P. Jantke and A. Shinohara, editors, Proc. The Fourth International Conference on Discovery Science, volume 2226 of LNAI, pages 435\u2013440. Springer-Verlag, 2001.","DOI":"10.1007\/3-540-45650-3_37"},{"key":"14_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/3-540-48194-X_16","volume-title":"Proc. 12th Annual Symposium on Combinatorial Pattern Matching (CPM\u201901)","author":"S. Inenaga","year":"2001","unstructured":"S. Inenaga, H. Hoshino, A. Shinohara, M. Takeda, S. Arikawa, G. Mauri, and G. Pavesi. On-line construction of compact directed acyclic word graphs. In A. Amir and G. M. Landau, editors, Proc. 12th Annual Symposium on Combinatorial Pattern Matching (CPM\u201901), volume 2089 of LNCS, pages 169\u2013180. Springer-Verlag, 2001."},{"key":"14_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/3-540-60044-2_43","volume-title":"Proc. 6th Annual Symposium on Combinatorial Pattern Matching (CPM\u201995)","author":"J. K\u00e4rkk\u00e4inen","year":"1995","unstructured":"J. K\u00e4rkk\u00e4inen. Suffix cactus: A cross between suffix tree and suffix array. In Z. Galil and E. Ukkonen, editors, Proc. 6th Annual Symposium on Combinatorial Pattern Matching (CPM\u201995), volume 973 of LNCS, pages 191\u2013204. Springer-Verlag, 1995."},{"key":"14_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/3-540-45123-4_26","volume-title":"Proc. 11th Annual Symposium on Combinatorial Pattern Matching (CPM\u201900)","author":"V. M\u00e4kinen","year":"2000","unstructured":"V. M\u00e4kinen. Compact suffix array. In R. Giancarlo and D. Sankoff, editors, Proc. 11th Annual Symposium on Combinatorial Pattern Matching (CPM\u201900), volume 1848 of LNCS, pages 305\u2013319. Springer-Verlag, 2000."},{"issue":"5","key":"14_CR14","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"U. Manber and G. Myers. Suffix arrays: A new method for on-line string searches. SIAM J. Compt., 22(5):935\u2013948, 1993.","journal-title":"SIAM J. Compt."},{"key":"14_CR15","unstructured":"H. Mannila, H. Toivonen, and A. I. Verkamo. Discovering frequent episode in sequences. In U. M. Fayyad and R. Uthurusamy, editors, Proc. 1st International Conference on Knowledge Discovery and Data Mining, pages 210\u2013215. AAAI Press, Aug. 1995."},{"issue":"2","key":"14_CR16","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E. M. McCreight","year":"1976","unstructured":"E. M. McCreight. A space-economical suffix tree construction algorithm. J. ACM, 23(2):262\u2013272, Apr. 1976.","journal-title":"J. ACM"},{"issue":"1","key":"14_CR17","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(92)90142-3","volume":"92","author":"D. Revuz","year":"1992","unstructured":"D. Revuz. Minimization of acyclic deterministic automata in linear time. Theoretical Computer Science, 92(1):181\u2013189, Jan. 1992.","journal-title":"Theoretical Computer Science"},{"key":"14_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/3-540-40996-3_35","volume-title":"Proc. of 11th International Symposium on Algorithms and Computation (ISAAC\u201900)","author":"K. Sadakane","year":"2000","unstructured":"K. Sadakane. Compressed text databases with efficient query algorithms based on the compressed suffix array. In Proc. of 11th International Symposium on Algorithms and Computation (ISAAC\u201900), volume 1969 of LNCS, pages 410\u2013421. Springer-Verlag, 2000."},{"key":"14_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/3-540-48194-X_12","volume-title":"Proc. 12th Annual Symposium on Combinatorial Pattern Matching (CPM\u201901)","author":"Z. Tron\u00ed\u010dek","year":"2001","unstructured":"Z. Tron\u00ed\u010dek. Episode matching. In A. Amir and G. M. Landau, editors, Proc. 12th Annual Symposium on Combinatorial Pattern Matching (CPM\u201901), volume 2089 of LNCS, pages 143\u2013146. Springer-Verlag, 2001."},{"issue":"3","key":"14_CR20","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E. Ukkonen","year":"1995","unstructured":"E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249\u2013260, 1995.","journal-title":"Algorithmica"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"P. Weiner. Linear pattern matching algorithms. In Proc. 14th Annual Symposium on Switching and Automata Theory, pages 1\u201311, Oct. 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-45452-7_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T13:10:32Z","timestamp":1550322632000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45452-7_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438625","9783540454526"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-45452-7_14","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}