{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T18:00:48Z","timestamp":1768586448503,"version":"3.49.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,5,9]],"date-time":"2020-05-09T00:00:00Z","timestamp":1588982400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,5,9]],"date-time":"2020-05-09T00:00:00Z","timestamp":1588982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18K18002"],"award-info":[{"award-number":["JP18K18002"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17H01697"],"award-info":[{"award-number":["JP17H01697"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP16H02783"],"award-info":[{"award-number":["JP16H02783"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18H04098"],"award-info":[{"award-number":["JP18H04098"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJPR1922"],"award-info":[{"award-number":["JPMJPR1922"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s00224-020-09980-x","type":"journal-article","created":{"date-parts":[[2020,5,9]],"date-time":"2020-05-09T12:02:37Z","timestamp":1589025757000},"page":"1273-1291","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings"],"prefix":"10.1007","volume":"64","author":[{"given":"Kiichi","family":"Watanabe","sequence":"first","affiliation":[]},{"given":"Yuto","family":"Nakashima","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":[[2020,5,9]]},"reference":[{"issue":"1&2","key":"9980_CR1","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0304-3975(94)00083-U","volume":"141","author":"A Apostolico","year":"1995","unstructured":"Apostolico, A., Breslauer, D., Galil, Z.: Parallel detection of all palindromes in a string. Theor Comput. Sci. 141(1&2), 163\u2013173 (1995)","journal-title":"Theor Comput. Sci."},{"issue":"1","key":"9980_CR2","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1006\/jcss.2002.1822","volume":"65","author":"P Beame","year":"2002","unstructured":"Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci. 65(1), 38\u201372 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"9980_CR3","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Proceedings of the 4th Latin American Symposium on Theoretical Informatics, LATIN 2000, pp. 88\u201394 (2000)","DOI":"10.1007\/10719839_9"},{"issue":"1-2","key":"9980_CR4","doi-asserted-by":"crossref","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-2), 539\u2013553 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"9980_CR5","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.tcs.2017.08.002","volume":"700","author":"A Ganguly","year":"2017","unstructured":"Ganguly, A., Hon, W., Shah, R., Thankachan, S.V.: Space-time trade-offs for finding shortest unique substrings and maximal unique matches. Theor. Comput. Sci. 700, 75\u201388 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"9980_CR6","doi-asserted-by":"crossref","unstructured":"Hon, W.-K., Thankachan, S.V., Xu, B.: An in-place framework for exact and approximate shortest unique substring queries. In: ISAAC 2015, pp. 755\u2013767 (2015)","DOI":"10.1007\/978-3-662-48971-0_63"},{"key":"9980_CR7","doi-asserted-by":"crossref","unstructured":"Hu, X., Pei, J., Tao, Y.: Shortest unique queries on strings. In: SPIRE 2014, pp. 161\u2013172 (2014)","DOI":"10.1007\/978-3-319-11918-2_16"},{"key":"9980_CR8","doi-asserted-by":"crossref","unstructured":"Ileri, A.M., K\u00fclekci, M.O., Xu, B.: Shortest unique substring query revisited. In: CPM 2014, pp. 172\u2013181 (2014)","DOI":"10.1007\/978-3-319-07566-2_18"},{"key":"9980_CR9","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.jda.2018.11.009","volume":"52-53","author":"H Inoue","year":"2018","unstructured":"Inoue, H., Nakashima, Y., Mieno, T., Inenaga, S., Bannai, H., Takeda, M.: Algorithms and combinatorial properties on shortest unique palindromic substrings. Journal of Discrete Algorithms 52-53, 122\u2013132 (2018)","journal-title":"Journal of Discrete Algorithms"},{"key":"9980_CR10","doi-asserted-by":"crossref","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"},{"issue":"8","key":"9980_CR11","doi-asserted-by":"crossref","first-page":"900","DOI":"10.1016\/j.tcs.2008.12.016","volume":"410","author":"W Matsubara","year":"2009","unstructured":"Matsubara, W., Inenaga, S., Ishino, A., Shinohara, A., Nakamura, T., Hashimoto, K.: Efficient algorithms to compute compressed longest common substrings and compressed palindromes. Theor. Comput. Sci. 410(8), 900\u2013913 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9980_CR12","unstructured":"Mieno, T., Inenaga, S., Bannai, H., Takeda, M.: Shortest unique substring queries on run-length encoded strings. In: Proc. MFCS 2016, pp. 69:1\u201369:11 (2016)"},{"key":"9980_CR13","unstructured":"Pei, J., Wu, W.C.-H., Yeh, M.-Y.: On Shortest Unique Substring Queries. In: Proc. ICDE 2013, pp. 937\u2013948 (2013)"},{"key":"9980_CR14","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/j.ejc.2017.07.021","volume":"68","author":"M Rubinchik","year":"2018","unstructured":"Rubinchik, M., Shur, A.M.: Eertree: an efficient data structure for processing palindromes in strings. Eur. J. Comb. 68, 249\u2013265 (2018)","journal-title":"Eur. J. Comb."},{"key":"9980_CR15","doi-asserted-by":"crossref","unstructured":"Tsuruta, K., Inenaga, S., Bannai, H., Takeda, M.: Shortest unique substrings queries in optimal time. In: Proc. SOFSEM 2014, pp. 503\u2013513 (2014)","DOI":"10.1007\/978-3-319-04298-5_44"},{"key":"9980_CR16","doi-asserted-by":"crossref","unstructured":"Watanabe, K., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Shortest unique palindromic substring queries on run-length encoded strings. In: IWOCA 2019, pp. 430\u2013441 (2019)","DOI":"10.1007\/978-3-030-25005-8_35"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09980-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-09980-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09980-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,8]],"date-time":"2021-05-08T23:21:37Z","timestamp":1620516097000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-09980-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,9]]},"references-count":16,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["9980"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-09980-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,9]]},"assertion":[{"value":"9 May 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}