{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T04:15:35Z","timestamp":1745554535054,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T00:00:00Z","timestamp":1648771200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T00:00:00Z","timestamp":1648771200000},"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":["25240003"],"award-info":[{"award-number":["25240003"]}],"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":["26280003"],"award-info":[{"award-number":["26280003"]}],"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":["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":["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":["JP18H04098"],"award-info":[{"award-number":["JP18H04098"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009023","name":"Precursory Research for Embryonic Science and Technology","doi-asserted-by":"publisher","award":["JPMJPR1922"],"award-info":[{"award-number":["JPMJPR1922"]}],"id":[{"id":"10.13039\/501100009023","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":[[2022,4]]},"DOI":"10.1007\/s00224-022-10070-3","type":"journal-article","created":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T08:19:45Z","timestamp":1649665185000},"page":"484-501","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Factorizing Strings into Repetitions"],"prefix":"10.1007","volume":"66","author":[{"given":"Hiroe","family":"Inoue","sequence":"first","affiliation":[]},{"given":"Yoshiaki","family":"Matsuoka","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6269-9353","authenticated-orcid":false,"given":"Yuto","family":"Nakashima","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1833-010X","authenticated-orcid":false,"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":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6138-1607","authenticated-orcid":false,"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,11]]},"reference":[{"key":"10070_CR1","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.dam.2016.04.009","volume":"212","author":"G Badkobeh","year":"2016","unstructured":"Badkobeh, G., Bannai, H., Goto, K., I, T., Iliopoulos, C.S., Inenaga, S., Puglisi, S.J., Sugimoto, S.: Closed factorization. Discret. Appl. Math. 212, 23\u201329 (2016)","journal-title":"Discret. Appl. Math."},{"issue":"5","key":"10070_CR2","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1137\/15M1011032","volume":"46","author":"H Bannai","year":"2017","unstructured":"Bannai, H., I, T., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: The \u201cruns\u201d theorem. SIAM J. Comput. 46(5), 1501\u20131514 (2017)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10070_CR3","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1142\/S0129054118400014","volume":"29","author":"H Bannai","year":"2018","unstructured":"Bannai, H., Gagie, T., Inenaga, S., K\u00e4rkk\u00e4inen, J., Kempa, D., Piatkowski, M., Sugimoto, S.: Diverse palindromic factorization is NP-complete. Int. J. Found. Comput. Sci. 29(2), 143\u2013164 (2018)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10070_CR4","unstructured":"Borozdin, K., Kosolobov, D., Rubinchik, M., Shur, A.M.: Palindromic Length in Linear Time. In: CPM 2017, pp. 23:1\u201323:12 (2017)"},{"issue":"1","key":"10070_CR5","doi-asserted-by":"publisher","first-page":"81","DOI":"10.2307\/1970044","volume":"68","author":"KT Chen","year":"1958","unstructured":"Chen, K.T., Fox, R.H., Lyndon, R.C.: Free differential calculus. iv. The quotient groups of the lower central series. Ann. Math. 68(1), 81\u201395 (1958)","journal-title":"Ann. Math."},{"issue":"2","key":"10070_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). https:\/\/doi.org\/10.1016\/j.ipl.2007.10.006","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"10070_CR7","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/BF01190846","volume":"13","author":"M Crochemore","year":"1995","unstructured":"Crochemore, M., Rytter, W.: Sqares, cubes, and time-space efficient string searching. Algorithmica 13(5), 405\u2013425 (1995)","journal-title":"Algorithmica"},{"key":"10070_CR8","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Ilie, L., Smyth, W.F.: A simple algorithm for computing the Lempel Ziv factorization. In: Proceedings of DCC 2008, pp. 482\u2013488 (2008)","DOI":"10.1109\/DCC.2008.36"},{"key":"10070_CR9","first-page":"81","volume":"20","author":"LJ Cummings","year":"1996","unstructured":"Cummings, L.J., Moore, D., Karhum\u00e4ki, J.: Borders of Fibonacci strings. J. Comb. Math. Comb. Comput. 20, 81\u201388 (1996)","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"10070_CR10","doi-asserted-by":"crossref","unstructured":"Dumitran, M., Manea, F., Nowotka, D.: On prefix\/suffix-square free words. In: Proceedings of SPIRE, pp. 54\u201366 (2015)","DOI":"10.1007\/978-3-319-23826-5_6"},{"issue":"4","key":"10070_CR11","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0196-6774(83)90017-2","volume":"4","author":"J Duval","year":"1983","unstructured":"Duval, J.: Factorizing words over an ordered alphabet. J. Algorithms 4(4), 363\u2013381 (1983)","journal-title":"J. Algorithms"},{"key":"10070_CR12","unstructured":"Ellert, J., Fischer, J.: Linear time runs over general ordered alphabets. In: Bansal, N., Merelli, E., Worrell, J. (eds.) 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12\u201316, 2021, Glasgow, Scotland (Virtual Conference), LIPIcs, vol. 198, pp. 63:1\u201363:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"10070_CR13","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":"1","key":"10070_CR14","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1090\/S0002-9939-1965-0174934-9","volume":"16","author":"NJ Fine","year":"1965","unstructured":"Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proc. Am. Math. Soc. 16(1), 109\u2013114 (1965)","journal-title":"Proc. Am. Math. Soc."},{"issue":"1","key":"10070_CR15","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/S0304-3975(98)00252-7","volume":"218","author":"AS Fraenkel","year":"1999","unstructured":"Fraenkel, A.S., Simpson, J.: The exact number of squares in fibonacci words. Theor. Comput. Sci. 218(1), 95\u2013106 (1999)","journal-title":"Theor. Comput. Sci."},{"key":"10070_CR16","unstructured":"Inoue, H., Matsuoka, Y., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Computing smallest and largest repetition factorizations in O(n log n) time. In: Holub, J., Zd\u00e1rek, J. (eds.) Proceedings of the Prague Stringology Conference 2016, Prague, Czech Republic, August 29\u201331, 2016, pp. 135\u2013145 (2016)"},{"key":"10070_CR17","doi-asserted-by":"crossref","unstructured":"Kolpakov, R.M., Kucherov, G.: Finding maximal repetitions in a word in linear time. In: Proceedings of FOCS 1999, pp. 596\u2013604 (1999)","DOI":"10.1109\/SFFCS.1999.814634"},{"key":"10070_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jda.2017.10.004","volume":"46\u201347","author":"R Kolpakov","year":"2017","unstructured":"Kolpakov, R., Podolskiy, M., Posypkin, M., Khrapov, N.: Searching of gapped repeats and subrepetitions in a word. J. Discrete Algorithms 46\u201347, 1\u201315 (2017)","journal-title":"J. Discrete Algorithms"},{"key":"10070_CR19","unstructured":"Kufleitner, M.: On bijective variants of the Burrows-Wheeler transform. In: Proceedings of PSC 2009, pp. 65\u201379 (2009)"},{"key":"10070_CR20","unstructured":"Lothaire, M.: Combinatorics on Words. Addison-Wesley, Reading (1983)"},{"key":"10070_CR21","unstructured":"Matsuoka, Y., Inenaga, S., Bannai, H., Takeda, M., Manea, F.: Factorizing a string into squares in linear time. In: Proceedings of CPM 2016, pp. 27:1\u201327:12 (2016)"},{"issue":"9","key":"10070_CR22","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1016\/j.ipl.2015.04.002","volume":"115","author":"Y Nakashima","year":"2015","unstructured":"Nakashima, Y., Takagi, T., Inenaga, S., Bannai, H., Takeda, M.: Constructing LZ78 tries and position heaps in linear time for large alphabets. Inf. Process. Lett. 115(9), 655\u2013659 (2015)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"10070_CR23","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1145\/322344.322346","volume":"29","author":"J Storer","year":"1982","unstructured":"Storer, J., Szymanski, T.: Data compression via textual substitution. J. ACM 29(4), 928\u2013951 (1982)","journal-title":"J. ACM"},{"key":"10070_CR24","doi-asserted-by":"crossref","unstructured":"Tanimura, Y., Fujishige, Y., I, T., Inenaga, S., Bannai, H., Takeda, M.: A faster algorithm for computing maximal \u03b1-gapped repeats in a string. In: Proceedings of SPIRE 2015, pp. 124\u2013136 (2015)","DOI":"10.1007\/978-3-319-23826-5_13"},{"key":"10070_CR25","doi-asserted-by":"crossref","unstructured":"I, T., Sugimoto, S., Inenaga, S., Bannai, H., Takeda, M.: Computing palindromic factorizations and palindromic covers on-line. In: Proceedings of CPM 2014, pp. 150\u2013161 (2014)","DOI":"10.1007\/978-3-319-07566-2_16"},{"key":"10070_CR26","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1109\/MC.1984.1659158","volume":"17","author":"TA Welch","year":"1984","unstructured":"Welch, T.A.: A technique for high performance data compression. IEEE Comput. 17, 8\u201319 (1984)","journal-title":"IEEE Comput."},{"issue":"3","key":"10070_CR27","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"IT-23","author":"J Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory IT-23(3), 337\u2013349 (1977)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"10070_CR28","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-length coding. IEEE Trans. Inf. Theory 24(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10070-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-022-10070-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10070-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T22:42:45Z","timestamp":1726958565000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-022-10070-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10070"],"URL":"https:\/\/doi.org\/10.1007\/s00224-022-10070-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2022,4]]},"assertion":[{"value":"25 January 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}