{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T09:39:09Z","timestamp":1776764349789,"version":"3.51.2"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T00:00:00Z","timestamp":1770595200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T00:00:00Z","timestamp":1770595200000},"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":["JP23H04381"],"award-info":[{"award-number":["JP23H04381"]}],"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":["JP21K17705"],"award-info":[{"award-number":["JP21K17705"]}],"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":["JP20H05964"],"award-info":[{"award-number":["JP20H05964"]}],"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,3]]},"DOI":"10.1007\/s00224-025-10255-6","type":"journal-article","created":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T11:43:22Z","timestamp":1770637402000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Subsequence Matching and LCS under Cartesian-Tree Equivalence"],"prefix":"10.1007","volume":"70","author":[{"given":"Taketo","family":"Tsujimoto","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuki","family":"Yonemoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroki","family":"Shibata","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takuya","family":"Mieno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuto","family":"Nakashima","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,9]]},"reference":[{"key":"10255_CR1","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., 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."},{"issue":"12","key":"10255_CR2","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., Kulczynski, T., Radoszewski, J., Rytter, W., Walen, T.: A linear time algorithm for consecutive permutation pattern matching. Inf. Process. Lett. 113(12), 430\u2013433 (2013)","journal-title":"Inf. Process. Lett."},{"key":"10255_CR3","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":"10255_CR4","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: STOC 1984, pp. 135\u2013143 (1984)","DOI":"10.1145\/800057.808675"},{"key":"10255_CR5","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."},{"key":"10255_CR6","unstructured":"Gawrychowski, P., Ghazawi, S., Landau, G.M.: On indeterminate strings matching. In: CPM 2020. LIPIcs, vol. 161, pp. 14\u201311414 (2020)"},{"key":"10255_CR7","doi-asserted-by":"publisher","unstructured":"Das, G., Fleischer, R., Gasieniec, L., Gunopulos, D., K\u00e4rkk\u00e4inen, J.: Episode matching. In: Combinatorial Pattern Matching, 8th Annual Symposium, CPM 97, Aarhus, Denmark, June 30 - July 2, 1997, Proceedings. Lecture Notes in Computer Science, vol. 1264, pp. 12\u201327 (1997). https:\/\/doi.org\/10.1007\/3-540-63220-4_46","DOI":"10.1007\/3-540-63220-4_46"},{"key":"10255_CR8","unstructured":"Oizumi, T., Kai, T., Mieno, T., Inenaga, S., Arimura, H.: Cartesian tree subsequence matching. In: CPM 2022. LIPIcs, vol. 223, pp. 14\u201311418 (2022)"},{"issue":"5","key":"10255_CR9","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0020-0190(97)00209-3","volume":"65","author":"P Bose","year":"1998","unstructured":"Bose, P., Buss, J.F., Lubiw, A.: Pattern matching for permutations. Inf. Process. Lett. 65(5), 277\u2013283 (1998)","journal-title":"Inf. Process. Lett."},{"key":"10255_CR10","doi-asserted-by":"publisher","unstructured":"Bille, P., G\u00f8rtz, I.L., Mozes, S., Steiner, T.A., Weimann, O.: The fine-grained complexity of episode matching. In: CPM 2022, pp. 4\u2013141 (2022). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2022.4","DOI":"10.4230\/LIPIcs.CPM.2022.4"},{"key":"10255_CR11","doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Quadratic conditional lower bounds for string problems and dynamic time warping. In: FOCS 2015, pp. 79\u201397 (2015)","DOI":"10.1109\/FOCS.2015.15"},{"issue":"1","key":"10255_CR12","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"WJ Masek","year":"1980","unstructured":"Masek, W.J., Paterson, M.S.: A faster algorithm computing string edit distances. J. Comput. Syst. Sci. 20(1), 18\u201331 (1980). https:\/\/doi.org\/10.1016\/0022-0000(80)90002-1","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"10255_CR13","first-page":"1209","volume":"11","author":"V Arlazarov","year":"1970","unstructured":"Arlazarov, V., Dinic, E., Kronrod, M., Faradzev, I.: On economical construction of the transitive closure of a directed graph. Soviet Mathematics Doklady 11(5), 1209\u20131210 (1970)","journal-title":"Soviet Mathematics Doklady"},{"issue":"5","key":"10255_CR14","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"JW Hunt","year":"1977","unstructured":"Hunt, J.W., Szymanski, T.G.: A fast algorithm for computing longest common subsequences. Commun. ACM 20(5), 350\u2013353 (1977)","journal-title":"Commun. ACM"},{"key":"10255_CR15","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF00264437","volume":"18","author":"N Nakatsu","year":"1982","unstructured":"Nakatsu, N., Kambayashi, Y., Yajima, S.: A longest common subsequence algorithm suitable for similar text strings. Acta Inf. 18, 171\u2013179 (1982)","journal-title":"Acta Inf."},{"issue":"1","key":"10255_CR16","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(92)90132-Y","volume":"92","author":"A Apostolico","year":"1992","unstructured":"Apostolico, A., Browne, S., Guerra, C.: Fast linear-space computations of longest common subsequences. Theor. Comput. Sci. 92(1), 3\u201317 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"10255_CR17","doi-asserted-by":"crossref","unstructured":"Sakai, Y.: Computing the longest common subsequence of two run-length encoded strings. In: ISAAC 2012, pp. 197\u2013206 (2012)","DOI":"10.1007\/978-3-642-35261-4_23"},{"key":"10255_CR18","doi-asserted-by":"publisher","unstructured":"Tsujimoto, T., Shibata, H., Mieno, T., Nakashima, Y., Inenaga, S.: Computing longest common subsequence under Cartesian-tree matching model. In: IWOCA 2024. Lecture Notes in Computer Science, vol. 14764, pp. 369\u2013381 (2024). https:\/\/doi.org\/10.1007\/978-3-031-63021-7_28","DOI":"10.1007\/978-3-031-63021-7_28"},{"issue":"1","key":"10255_CR19","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1145\/322290.322295","volume":"29","author":"CM Hoffmann","year":"1982","unstructured":"Hoffmann, C.M., O\u2019Donnell, M.J.: Pattern matching in trees. J. ACM 29(1), 68\u201395 (1982). https:\/\/doi.org\/10.1145\/322290.322295","journal-title":"J. ACM"},{"issue":"2","key":"10255_CR20","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/JCSS.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/JCSS.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"2\u20133","key":"10255_CR21","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/J.TCS.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2\u20133), 357\u2013365 (2005). https:\/\/doi.org\/10.1016\/J.TCS.2005.09.023","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10255-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10255-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10255-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T08:42:17Z","timestamp":1776760937000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10255-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,9]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10255"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10255-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,9]]},"assertion":[{"value":"11 March 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":"9 February 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":"7"}}