{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:29Z","timestamp":1759637909272,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030326852"},{"type":"electronic","value":"9783030326869"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-32686-9_27","type":"book-chapter","created":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T18:02:27Z","timestamp":1570212147000},"page":"382-391","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets"],"prefix":"10.1007","author":[{"given":"Noriki","family":"Fujisato","sequence":"first","affiliation":[]},{"given":"Yuto","family":"Nakashima","sequence":"additional","affiliation":[]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6856-5185","authenticated-orcid":false,"given":"Hideo","family":"Bannai","sequence":"additional","affiliation":[]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,10,3]]},"reference":[{"key":"27_CR1","first-page":"49","volume":"24","author":"BS Baker","year":"1992","unstructured":"Baker, B.S.: A program for identifying duplicated code. Comput. Sci. Stat. 24, 49\u201357 (1992)","journal-title":"Comput. Sci. Stat."},{"issue":"1","key":"27_CR2","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1006\/jcss.1996.0003","volume":"52","author":"BS Baker","year":"1996","unstructured":"Baker, B.S.: Parameterized pattern matching: algorithms and applications. J. Comput. Syst. Sci. 52(1), 28\u201342 (1996). \n                      https:\/\/doi.org\/10.1006\/jcss.1996.0003\n                      \n                    . \n                      https:\/\/doi.org\/10.1006\/jcss.1996.0003","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"27_CR3","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1137\/S0097539793246707","volume":"26","author":"BS Baker","year":"1997","unstructured":"Baker, B.S.: Parameterized duplication in strings: algorithms and an application to software maintenance. SIAM J. Comput. 26(5), 1343\u20131362 (1997). \n                      https:\/\/doi.org\/10.1137\/S0097539793246707","journal-title":"SIAM J. Comput."},{"key":"27_CR4","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.jda.2012.05.004","volume":"16","author":"R Beal","year":"2012","unstructured":"Beal, R., Adjeroh, D.: Variations of the parameterized longest previous factor. J. Discrete Algorithms 16, 129\u2013150 (2012). \n                      https:\/\/doi.org\/10.1016\/j.jda.2012.05.004\n                      \n                    . \n                      http:\/\/www.sciencedirect.com\/science\/article\/pii\/S1570866712001013\n                      \n                    , selected papers from the 22nd International Workshop on Combinatorial Algorithms (IWOCA 2011)","journal-title":"J. Discrete Algorithms"},{"key":"27_CR5","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.jda.2012.05.001","volume":"16","author":"R Beal","year":"2012","unstructured":"Beal, R., Adjeroh, D.A.: p-suffix sorting as arithmetic coding. J. Discrete Algorithms 16, 151\u2013169 (2012). \n                      https:\/\/doi.org\/10.1016\/j.jda.2012.05.001","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"27_CR6","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.ipl.2007.10.006","volume":"106","author":"M Crochemore","year":"2008","unstructured":"Crochemore, M., Ilie, L.: Computing longest previous factor in linear time and applications. Inf. Process. Lett. 106(2), 75\u201380 (2008). \n                      https:\/\/doi.org\/10.1016\/j.ipl.2007.10.006\n                      \n                    . \n                      http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0020019007002979","journal-title":"Inf. Process. Lett."},{"key":"27_CR7","unstructured":"Deguchi, S., Higashijima, F., Bannai, H., Inenaga, S., Takeda, M.: Parameterized suffix arrays for binary strings. In: Holub, J., Zd\u00e1rek, J. (eds.) Proceedings of the Prague Stringology Conference 2008, Prague, Czech Republic, 1\u20133 September 2008. pp. 84\u201394. Prague Stringology Club, Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague (2008), \n                      http:\/\/www.stringology.org\/event\/2008\/p08.html"},{"key":"27_CR8","doi-asserted-by":"publisher","unstructured":"Diptarama, Katsura, T., Otomo, Y., Narisawa, K., Shinohara, A.: Position heaps for parameterized strings. In: K\u00e4rkk\u00e4inen, J., Radoszewski, J., Rytter, W. (eds.) 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, July 4\u20136, 2017, Warsaw, Poland. LIPIcs, vol. 78, pp. 8:1\u20138:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). \n                      https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2017.8\n                      \n                    , \n                      https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2017.8","DOI":"10.4230\/LIPIcs.CPM.2017.8 10.4230\/LIPIcs.CPM.2017.8"},{"issue":"1","key":"27_CR9","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.jda.2010.12.001","volume":"9","author":"A Ehrenfeucht","year":"2011","unstructured":"Ehrenfeucht, A., McConnell, R.M., Osheim, N., Woo, S.W.: Position heaps: a simple and dynamic text indexing data structure. J. Discrete Algorithms 9(1), 100\u2013121 (2011). \n                      https:\/\/doi.org\/10.1016\/j.jda.2010.12.001\n                      \n                    . \n                      http:\/\/www.sciencedirect.com\/science\/article\/pii\/S1570866710000535\n                      \n                    , 20th Anniversary Edition of the Annual Symposium on Combinatorial Pattern Matching (CPM 2009)","journal-title":"J. Discrete Algorithms"},{"key":"27_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/11780441_5","volume-title":"Combinatorial Pattern Matching","author":"J Fischer","year":"2006","unstructured":"Fischer, J., Heun, V.: Theoretical and practical improvements on the RMQ-Problem, with applications to LCA and LCE. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol. 4009, pp. 36\u201348. Springer, Heidelberg (2006). \n                      https:\/\/doi.org\/10.1007\/11780441_5"},{"key":"27_CR11","unstructured":"Fujisato, N., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Right-to-left online construction of parameterized position heaps. CoRR abs\/1808.01071 (2018). \n                      http:\/\/arxiv.org\/abs\/1808.01071"},{"key":"27_CR12","doi-asserted-by":"publisher","unstructured":"Ganguly, A., Hon, W., Huang, Y., Pissis, S.P., Shah, R., Thankachan, S.V.: Parameterized text indexing with one wildcard. In: 2019 Data Compression Conference (DCC), pp. 152\u2013161. March 2019. \n                      https:\/\/doi.org\/10.1109\/DCC.2019.00023","DOI":"10.1109\/DCC.2019.00023"},{"key":"27_CR13","doi-asserted-by":"publisher","unstructured":"Ganguly, A., Shah, R., Thankachan, S.V.: pbwt: achieving succinct data structures for parameterized pattern matching and related problems. In: Klein, P.N. (ed.) Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16\u201319, pp. 397\u2013407. SIAM (2017). \n                      https:\/\/doi.org\/10.1137\/1.9781611974782.25\n                      \n                    , \n                      https:\/\/doi.org\/10.1137\/1.9781611974782.25","DOI":"10.1137\/1.9781611974782.25 10.1137\/1.9781611974782.25"},{"key":"27_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/978-3-642-10217-2_31","volume-title":"Combinatorial Algorithms","author":"T I","year":"2009","unstructured":"I, T., Deguchi, S., Bannai, H., Inenaga, S., Takeda, M.: Lightweight parameterized suffix array construction. In: Fiala, J., Kratochv\u00edl, J., Miller, M. (eds.) IWOCA 2009. LNCS, vol. 5874, pp. 312\u2013323. Springer, Heidelberg (2009). \n                      https:\/\/doi.org\/10.1007\/978-3-642-10217-2_31"},{"issue":"6","key":"27_CR15","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53(6), 918\u2013936 (2006). \n                      https:\/\/doi.org\/10.1145\/1217856.1217858","journal-title":"J. ACM"},{"key":"27_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume-title":"Combinatorial Pattern Matching","author":"T Kasai","year":"2001","unstructured":"Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Amir, A. (ed.) CPM 2001. LNCS, vol. 2089, pp. 181\u2013192. Springer, Heidelberg (2001). \n                      https:\/\/doi.org\/10.1007\/3-540-48194-X_17"},{"issue":"2\u20134","key":"27_CR17","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.jda.2004.08.019","volume":"3","author":"DK Kim","year":"2005","unstructured":"Kim, D.K., Sim, J.S., Park, H., Park, K.: Constructing suffix arrays in linear time. J. Discrete Algorithms 3(2\u20134), 126\u2013142 (2005). \n                      https:\/\/doi.org\/10.1016\/j.jda.2004.08.019","journal-title":"J. Discrete Algorithms"},{"issue":"2\u20134","key":"27_CR18","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.jda.2004.08.002","volume":"3","author":"P Ko","year":"2005","unstructured":"Ko, P., Aluru, S.: Space efficient linear time construction of suffix arrays. J. Discrete Algorithms 3(2\u20134), 143\u2013156 (2005). \n                      https:\/\/doi.org\/10.1016\/j.jda.2004.08.002","journal-title":"J. Discrete Algorithms"},{"key":"27_CR19","doi-asserted-by":"publisher","unstructured":"Kosaraju, S.R.: Faster algorithms for the construction of parameterized suffix trees (preliminary version). In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23\u201325 October 1995, pp. 631\u2013637. IEEE Computer Society (1995). \n                      https:\/\/doi.org\/10.1109\/SFCS.1995.492664","DOI":"10.1109\/SFCS.1995.492664"},{"issue":"1","key":"27_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-003-1067-9","volume":"39","author":"T Shibuya","year":"2004","unstructured":"Shibuya, T.: Generalization of a suffix tree for RNA structural pattern matching. Algorithmica 39(1), 1\u201319 (2004). \n                      https:\/\/doi.org\/10.1007\/s00453-003-1067-9","journal-title":"Algorithmica"},{"key":"27_CR21","doi-asserted-by":"publisher","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15\u201317, 1973, pp. 1\u201311. IEEE Computer Society (1973). \n                      https:\/\/doi.org\/10.1109\/SWAT.1973.13","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-32686-9_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T21:07:40Z","timestamp":1570223260000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-32686-9_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030326852","9783030326869"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-32686-9_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"3 October 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Segovia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 October 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 October 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/spire19.lbd.org.es\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"59","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"8","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"1","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}