{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T04:11:44Z","timestamp":1751602304276,"version":"3.41.0"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319788241"},{"type":"electronic","value":"9783319788258"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","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":[[2018]]},"DOI":"10.1007\/978-3-319-78825-8_32","type":"book-chapter","created":{"date-parts":[[2018,4,16]],"date-time":"2018-04-16T18:59:07Z","timestamp":1523905147000},"page":"397-408","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Shortest Unique Palindromic Substring Queries in Optimal Time"],"prefix":"10.1007","author":[{"given":"Yuto","family":"Nakashima","sequence":"first","affiliation":[]},{"given":"Hiroe","family":"Inoue","sequence":"additional","affiliation":[]},{"given":"Takuya","family":"Mieno","sequence":"additional","affiliation":[]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]},{"given":"Hideo","family":"Bannai","sequence":"additional","affiliation":[]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,4,17]]},"reference":[{"key":"32_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-319-21500-6_6","volume-title":"Developments in Language Theory","author":"H Bannai","year":"2015","unstructured":"Bannai, H., Gagie, T., Inenaga, S., K\u00e4rkk\u00e4inen, J., Kempa, D., Pi\u0105tkowski, M., Puglisi, S.J., Sugimoto, S.: Diverse palindromic factorization is NP-complete. In: Potapov, I. (ed.) DLT 2015. LNCS, vol. 9168, pp. 85\u201396. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21500-6_6"},{"key":"32_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"MA Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88\u201394. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/10719839_9"},{"issue":"1\u20132","key":"32_CR3","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1016\/S0304-3975(99)00320-5","volume":"255","author":"X Droubay","year":"2001","unstructured":"Droubay, X., Justin, J., Pirillo, G.: Episturmian words and some constructions of de Luca and Rauzy. Theor. Comput. Sci. 255(1\u20132), 539\u2013553 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"32_CR4","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.jda.2014.08.001","volume":"28","author":"G Fici","year":"2014","unstructured":"Fici, G., Gagie, T., K\u00e4rkk\u00e4inen, J., Kempa, D.: A subquadratic algorithm for minimum palindromic factorization. J. Discrete Algorithms 28, 41\u201348 (2014)","journal-title":"J. Discrete Algorithms"},{"issue":"20","key":"32_CR5","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1016\/j.ipl.2010.07.018","volume":"110","author":"R Groult","year":"2010","unstructured":"Groult, R., Prieur, \u00c9., Richomme, G.: Counting distinct palindromes in a word in linear time. Inf. Process. Lett. 110(20), 908\u2013912 (2010)","journal-title":"Inf. Process. Lett."},{"key":"32_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1007\/978-3-662-48971-0_63","volume-title":"Algorithms and Computation","author":"W-K Hon","year":"2015","unstructured":"Hon, W.-K., Thankachan, S.V., Xu, B.: An in-place framework for exact and approximate shortest unique substring queries. In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 755\u2013767. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48971-0_63"},{"key":"32_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/978-3-319-11918-2_16","volume-title":"String Processing and Information Retrieval","author":"X Hu","year":"2014","unstructured":"Hu, X., Pei, J., Tao, Y.: Shortest unique queries on strings. In: Moura, E., Crochemore, M. (eds.) SPIRE 2014. LNCS, vol. 8799, pp. 161\u2013172. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11918-2_16"},{"key":"32_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-319-07566-2_16","volume-title":"Combinatorial Pattern Matching","author":"T I","year":"2014","unstructured":"I, T., Sugimoto, S., Inenaga, S., Bannai, H., Takeda, M.: Computing palindromic factorizations and palindromic covers on-line. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 150\u2013161. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07566-2_16"},{"key":"32_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-319-07566-2_18","volume-title":"Combinatorial Pattern Matching","author":"AM \u0130leri","year":"2014","unstructured":"\u0130leri, A.M., K\u00fclekci, M.O., Xu, B.: Shortest unique substring query revisited. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 172\u2013181. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07566-2_18"},{"issue":"11","key":"32_CR10","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1111\/j.1349-7006.1992.tb02734.x","volume":"83","author":"E Kuramoto","year":"1992","unstructured":"Kuramoto, E., Yano, O., Kimura, Y., Baba, M., Makino, T., Yamamoto, S., Yamamoto, T., Kataoka, T., Tokunaga, T.: Oligonucleotide sequences required for natural killer cell activation. Jpn. J. Cancer Res. 83(11), 1128\u20131131 (1992)","journal-title":"Jpn. J. Cancer Res."},{"key":"32_CR11","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1145\/321892.321896","volume":"22","author":"G Manacher","year":"1975","unstructured":"Manacher, G.: A new linear-time \u201con-line\u201d algorithm for finding the smallest initial palindrome of a string. J. ACM 22, 346\u2013351 (1975)","journal-title":"J. ACM"},{"key":"32_CR12","unstructured":"Mieno, T., Inenaga, S., Bannai, H., Takeda, M.: Shortest unique substring queries on run-length encoded strings. In: Proceedings of MFCS 2016, pp. 69:1\u201369:11 (2016)"},{"key":"32_CR13","doi-asserted-by":"crossref","unstructured":"Pei, J., Wu, W.C.H., Yeh, M.Y.: On shortest unique substring queries. In: Proceedings of ICDE 2013, pp. 937\u2013948 (2013)","DOI":"10.1109\/ICDE.2013.6544887"},{"key":"32_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-319-29516-9_27","volume-title":"Combinatorial Algorithms","author":"M Rubinchik","year":"2016","unstructured":"Rubinchik, M., Shur, A.M.: EERTREE: an efficient data structure for processing palindromes in strings. In: Lipt\u00e1k, Z., Smyth, W.F. (eds.) IWOCA 2015. LNCS, vol. 9538, pp. 321\u2013333. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-29516-9_27"},{"key":"32_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/978-3-319-04298-5_44","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"K Tsuruta","year":"2014","unstructured":"Tsuruta, K., Inenaga, S., Bannai, H., Takeda, M.: Shortest unique substrings queries in optimal time. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 503\u2013513. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-04298-5_44"},{"issue":"12","key":"32_CR16","doi-asserted-by":"crossref","first-page":"4072","DOI":"10.4049\/jimmunol.148.12.4072","volume":"148","author":"S Yamamoto","year":"1992","unstructured":"Yamamoto, S., Yamamoto, T., Kataoka, T., Kuramoto, E., Yano, O., Tokunaga, T.: Unique palindromic sequences in synthetic oligonucleotides are required to induce IFN [correction of INF] and augment IFN-mediated [correction of INF] natural killer activity. J. Immunol. 148(12), 4072\u20134076 (1992)","journal-title":"J. Immunol."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-78825-8_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T18:22:44Z","timestamp":1751566964000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-78825-8_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319788241","9783319788258"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-78825-8_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"17 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Newcastle","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Australia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 July 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 July 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/carma.newcastle.edu.au\/meetings\/iwoca\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}