{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T12:06:08Z","timestamp":1775909168017,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T00:00:00Z","timestamp":1775865600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T00:00:00Z","timestamp":1775865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["23H04378"],"award-info":[{"award-number":["23H04378"]}],"id":[{"id":"10.13039\/501100001691","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":[[2026,6]]},"DOI":"10.1007\/s00224-025-10257-4","type":"journal-article","created":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T11:37:18Z","timestamp":1775907438000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The ceBWT\u00a0Index: An Index for Circular Cartesian Tree Matching on Multiple Texts"],"prefix":"10.1007","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-0368-5008","authenticated-orcid":false,"given":"Eric M.","family":"Osterkamp","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8721-4444","authenticated-orcid":false,"given":"Dominik","family":"K\u00f6ppl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,11]]},"reference":[{"key":"10257_CR1","doi-asserted-by":"crossref","unstructured":"Auvray, B., David, J., Groult, R., Lecroq, T.: Approximate cartesian tree matching: An approach using swaps. In: Proc. SPIRE, volume 14240 of LNCS, pages 49\u201361 (2023)","DOI":"10.1007\/978-3-031-43980-3_5"},{"key":"10257_CR2","doi-asserted-by":"crossref","unstructured":"Boucher, C., Cenzato, D., Lipt\u00e1k, Z., Rossi, M., Sciortino, M.: r-indexing the eBWT. In: Proc. SPIRE, volume 12944 of LNCS, pages 3\u201312 (2021)","DOI":"10.1007\/978-3-030-86692-1_1"},{"issue":"4\/5","key":"10257_CR3","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF01185431","volume":"12","author":"WI Chang","year":"1994","unstructured":"Chang, W.I., Lawler, E.L.: Sublinear approximate string matching and biological applications. Algorithmica 12(4\/5), 327\u2013344 (1994)","journal-title":"Algorithmica"},{"key":"10257_CR4","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Rytter, W.: Jewels of Stringology: Text Algorithms. World Scientific (2002)","DOI":"10.1142\/4838"},{"issue":"3","key":"10257_CR5","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1007\/s00453-012-9683-x","volume":"68","author":"ED Demaine","year":"2014","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On Cartesian trees and range minimum queries. Algorithmica 68(3), 610\u2013625 (2014)","journal-title":"Algorithmica"},{"issue":"4","key":"10257_CR6","doi-asserted-by":"publisher","first-page":"907","DOI":"10.1093\/comjnl\/bxab204","volume":"66","author":"S Faro","year":"2022","unstructured":"Faro, S., Lecroq, T., Park, K., Scafiti, S.: On the longest common Cartesian substring problem. Comput. J. 66(4), 907\u2013923 (2022)","journal-title":"Comput. J."},{"key":"10257_CR7","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: Proc. FOCS, pages 390\u2013398 (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"issue":"1","key":"10257_CR8","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. Proceed. Am. Math. Soc. 16(1), 109\u2013114 (1965)","journal-title":"Proceed. Am. Math. Soc."},{"key":"10257_CR9","doi-asserted-by":"crossref","unstructured":"Fischer, J.: Optimal succinctness for range minimum queries. In: Proc. LATIN, volume 6034 of LNCS, pages 158\u2013169 (2010)","DOI":"10.1007\/978-3-642-12200-2_16"},{"key":"10257_CR10","unstructured":"Foster, P., Klapuri, A., Dixon, S. A method for identifying repetition structure in musical audio based on time series prediction. In: Proc. EUSIPCO, pages 1299\u20131303. IEEE (2012)"},{"key":"10257_CR11","doi-asserted-by":"crossref","unstructured":"Fu, T.C., Chung, F.L., Luk, R., Ng, C.M.: Stock time series pattern matching: Template-based vs. rule-based approaches. Eng. Appl. Artif. Intell. 20(3), 347\u2013364 (2007)","DOI":"10.1016\/j.engappai.2006.07.003"},{"key":"10257_CR12","doi-asserted-by":"crossref","unstructured":"Funakoshi, M., Mieno, T., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Computing maximal palindromes in non-standard matching models. In: Proc. IWOCA, volume 14764 of LNCS, pages 165\u2013179 (2024)","DOI":"10.1007\/978-3-031-63021-7_13"},{"key":"10257_CR13","unstructured":"Gawrychowski, P., Ghazawi, S., Landau, G.M.: On indeterminate strings matching. In: Proc. CPM, volume 161 of LIPIcs, pages 14:1\u201314:14 (2020)"},{"key":"10257_CR14","doi-asserted-by":"crossref","unstructured":"Hashimoto, D., Hendrian, D., K\u00f6ppl, D., Yoshinaka, R., Shinohara, A.: Computing the parameterized Burrows\u2013Wheeler transform online. In: Proc. SPIRE, volume 13617 of LNCS, pages 70\u201385 (2022)","DOI":"10.1007\/978-3-031-20643-6_6"},{"key":"10257_CR15","unstructured":"Hiraga, Y.: Structural recognition of music by pattern matching. In: Proc. ICMC. Michigan Publishing (1997)"},{"key":"10257_CR16","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Ku, T.H., Lu, C.H., Shah, R., Thankachan, S.V.: Efficient algorithm for circular Burrows\u2013Wheeler transform. In: Proc. CPM, volume 7354 of LNCS, pages 257\u2013268 (2012)","DOI":"10.1007\/978-3-642-31265-6_21"},{"key":"10257_CR17","unstructured":"Iseri, K., Hendrian, D., K\u00f6ppl, D., Yoshinaka, R., Shinohara, A.: Breaking a barrier in constructing compact indexes for parameterized pattern matching. In: Proc. ICALP, volume 297 of LIPIcs, pages 89:1\u201389:19 (2024)"},{"key":"10257_CR18","doi-asserted-by":"crossref","unstructured":"Kikuchi, N., Hendrian, D., Yoshinaka, R., Shinohara, A.: Computing covers under substring consistent equivalence relations. In: Proc. SPIRE, volume 12303 of LNCS, pages 131\u2013146 (2020)","DOI":"10.1007\/978-3-030-59212-7_10"},{"key":"10257_CR19","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.tcs.2013.10.006","volume":"525","author":"J Kim","year":"2014","unstructured":"Kim, J., Eades, P., Fleischer, R., Hong, S.H., Iliopoulos, C.S., Park, K., Puglisi, S.J., Tokuyama, T.: Order-preserving matching. Theor. Comput. Sci. 525, 68\u201379 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"10257_CR20","unstructured":"Kim, S.H., Cho, H. G.: A compact index for Cartesian tree matching. In: Proc. CPM, volume 191 of LIPIcs, pages 18:1\u201318:19 (2021)"},{"key":"10257_CR21","doi-asserted-by":"crossref","unstructured":"Kim, S., Han, Y.S.: Approximate Cartesian tree pattern matching. In: Proc. DLT, volume 14791 of LNCS, pages 189\u2013202 (2024)","DOI":"10.1007\/978-3-031-66159-4_14"},{"issue":"12","key":"10257_CR22","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/j.ipl.2013.03.015","volume":"113","author":"M Kubica","year":"2013","unstructured":"Kubica, M., Kulczy\u0144ski, T., Radoszewski, J., Rytter, W., Wale\u0144, T.: A linear time algorithm for consecutive permutation pattern matching. Inf. Process. Lett. 113(12), 430\u2013433 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"10257_CR23","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/j.tcs.2007.07.014","volume":"387","author":"S Mantaci","year":"2007","unstructured":"Mantaci, S., Restivo, A., Rosone, G., Sciortino, M.: An extension of the Burrows-Wheeler transform. Theor. Comput. Sci. 387(3), 298\u2013312 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"10257_CR24","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.tcs.2016.02.017","volume":"656","author":"Y Matsuoka","year":"2016","unstructured":"Matsuoka, Y., Aoki, T., Inenaga, S., Bannai, H., Takeda, M.: Generalized pattern matching and periodicity under substring consistent equivalence relations. Theor. Comput. Sci. 656, 225\u2013233 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"10257_CR25","doi-asserted-by":"crossref","unstructured":"Munro, I., Nekrich, Y., Vitter, J.S.: Dynamic data structures for document collections and graphs. In: Proc. PODS, pages 277\u2013289 (2015)","DOI":"10.1145\/2745754.2745778"},{"key":"10257_CR26","doi-asserted-by":"crossref","unstructured":"Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), 16:1\u201316:39 (2014)","DOI":"10.1145\/2601073"},{"key":"10257_CR27","doi-asserted-by":"crossref","unstructured":"Nishimoto, A., Fujisato, N., Nakashima, Y., Inenaga, S.: Position heaps for Cartesian-tree matching on strings and tries. In: Proc. SPIRE, volume 12944 of LNCS, pages 241\u2013254 (2021)","DOI":"10.1007\/978-3-030-86692-1_20"},{"key":"10257_CR28","doi-asserted-by":"crossref","unstructured":"Ohlebusch, E., Gog, S., K\u00fcgel, A.: Computing matching statistics and maximal exact matches on compressed full-text indexes. In: Proc. SPIRE, volume 6393 of LNCS, pages 347\u2013358 (2010)","DOI":"10.1007\/978-3-642-16321-0_36"},{"key":"10257_CR29","unstructured":"Tsubasa Oizumi, Takeshi Kai, Takuya Mieno, Shunsuke Inenaga, and Hiroki Arimura. Cartesian tree subsequence matching. In: Proc. CPM volume 223 of LIPIcs, pages 14:1\u201314:18 (2022)"},{"key":"10257_CR30","doi-asserted-by":"crossref","unstructured":"Osterkamp, E.M., K\u00f6ppl, D.: Extending the parameterized Burrows\u2013Wheeler transform. In Proc. DCC, pages 143\u2013152 (2024)","DOI":"10.1109\/DCC58796.2024.00022"},{"key":"10257_CR31","unstructured":"Osterkamp, E.M., K\u00f6ppl, D.: Extending the Burrows\u2013Wheeler transform for Cartesian tree matching and constructing it. In: Proc. CPM, volume 331 of LIPIcs, pages 26:1\u201326:17, 7 (2025)"},{"key":"10257_CR32","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.tcs.2020.09.014","volume":"845","author":"SG Park","year":"2020","unstructured":"Park, S.G., Bataa, M., Amir, A., Landau, G.M., Park, K.: Finding patterns and periods in Cartesian tree matching. Theor. Comput. Sci. 845, 181\u2013197 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"10257_CR33","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2020.10.009","volume":"849","author":"S Song","year":"2021","unstructured":"Song, S., Gu, G., Ryu, C., Faro, S., Lecroq, T., Park, K.: Fast algorithms for single and multiple pattern Cartesian tree matching. Theor. Comput. Sci. 849, 47\u201363 (2021)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"10257_CR34","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A unifying look at data structures. Commun. ACM 23(4), 229\u2013239 (1980)","journal-title":"Commun. ACM"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10257-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10257-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10257-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T11:37:20Z","timestamp":1775907440000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10257-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,11]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10257"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10257-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,11]]},"assertion":[{"value":"20 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"27"}}