{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T13:19:00Z","timestamp":1774271940990,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T00:00:00Z","timestamp":1771977600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T00:00:00Z","timestamp":1771977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2026,3]]},"DOI":"10.1007\/s00236-026-00523-4","type":"journal-article","created":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T10:34:33Z","timestamp":1772015673000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast algorithms for window accumulated subsequence matching problem"],"prefix":"10.1007","volume":"63","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2737-1317","authenticated-orcid":false,"given":"Zdenek","family":"Tronicek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,25]]},"reference":[{"key":"523_CR1","first-page":"11","volume":"367","author":"M Kosche","year":"2022","unstructured":"Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Combinatorial algorithms for subsequence matching: A survey. In:International Workshop on Non-Classical Models of Automata and Applications (NCMA) 367, 11\u201327 (2022)","journal-title":"In:International Workshop on Non-Classical Models of Automata and Applications (NCMA)"},{"issue":"4","key":"523_CR2","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1051\/ita\/1986200404411","volume":"20","author":"J-J Hebrard","year":"1986","unstructured":"Hebrard, J.-J., Crochemore, M.: Calcul de la distance par les sous-mots. RAIRO-Theoretical Informatics and Applications 20(4), 441\u2013456 (1986)","journal-title":"RAIRO-Theoretical Informatics and Applications"},{"issue":"2","key":"523_CR3","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0304-3975(91)90358-9","volume":"78","author":"RA Baeza-Yates","year":"1991","unstructured":"Baeza-Yates, R.A.: Searching subsequences. Theoret. Comput. Sci. 78(2), 363\u2013376 (1991)","journal-title":"Theoret. Comput. Sci."},{"issue":"3\u20134","key":"523_CR4","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S1570-8667(03)00029-7","volume":"1","author":"M Crochemore","year":"2003","unstructured":"Crochemore, M., Melichar, B., Tron\u00ed\u010dek, Z.: Directed acyclic subsequence graph\u2013overview. Journal of Discrete Algorithms 1(3\u20134), 255\u2013280 (2003)","journal-title":"Journal of Discrete Algorithms"},{"key":"523_CR5","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.jda.2017.05.001","volume":"44","author":"P Bille","year":"2017","unstructured":"Bille, P., G\u00f8rtz, I.L., Skjoldjensen, F.R.: Subsequence automata with default transitions. Journal of Discrete Algorithms 44, 48\u201355 (2017)","journal-title":"Journal of Discrete Algorithms"},{"key":"523_CR6","doi-asserted-by":"crossref","unstructured":"Kosche, M., Ko\u00df, T., Manea, F., Pak, V.: Subsequences in bounded ranges: matching and analysis problems. In: International Conference on Reachability Problems, 140\u2013159 (2022). Springer","DOI":"10.1007\/978-3-031-19135-0_10"},{"key":"523_CR7","unstructured":"Day, J.D., Kosche, M., Manea, F., Schmid, M.L.: Subsequences with gap constraints: Complexity bounds for matching and analysis problems. In: International Symposium on Algorithms and Computation (ISAAC), 64\u20131 (2022). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"523_CR8","unstructured":"Manea, F., Richardsen, J., Schmid, M.L.: Subsequences with generalised gap constraints: Upper and lower complexity bounds. In: Annual Symposium on Combinatorial Pattern Matching (CPM), 22\u20131 (2024). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"523_CR9","doi-asserted-by":"crossref","unstructured":"Yonemoto, Y., Mieno, T., Inenaga, S., Yoshinaka, R., Shinohara, A.: Subsequence matching and LCS with segment number constraints. In: International Conference on Algorithms and Complexity, 136\u2013150 (2025). Springer","DOI":"10.1007\/978-3-031-92935-9_9"},{"key":"523_CR10","unstructured":"Adamson, D., Fleischmann, P., Huch, A., Ko\u00df, T., Manea, F., Nowotka, D.: $$k$$-Universality of regular languages. In: International Symposium on Algorithms and Computation (ISAAC) (2023). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"523_CR11","unstructured":"Fazekas, S.Z., Ko\u00df, T., Manea, F., Merca\u015f, R., Specht, T.: Subsequence matching and analysis problems for formal languages. In: International Symposium on Algorithms and Computation (ISAAC), 28\u20131 (2024). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"issue":"5","key":"523_CR12","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1007\/s10958-009-9396-0","volume":"158","author":"A Tiskin","year":"2009","unstructured":"Tiskin, A.: Faster subsequence recognition in compressed strings. J. Math. Sci. 158(5), 759\u2013769 (2009)","journal-title":"J. Math. Sci."},{"key":"523_CR13","doi-asserted-by":"crossref","unstructured":"Tiskin, A.: Towards approximate matching in compressed strings: Local subsequence recognition. In: International Computer Science Symposium in Russia, 401\u2013414 (2011). Springer","DOI":"10.1007\/978-3-642-20712-9_32"},{"key":"523_CR14","doi-asserted-by":"crossref","unstructured":"Yamamoto, T., Bannai, H., Inenaga, S., Takeda, M.: Faster subsequence and don\u2019t-care pattern matching on compressed texts. In: Annual Symposium on Combinatorial Pattern Matching (CPM), 309\u2013322 (2011). Springer","DOI":"10.1007\/978-3-642-21458-5_27"},{"key":"523_CR15","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/s00453-015-0068-9","volume":"77","author":"P Bille","year":"2017","unstructured":"Bille, P., Cording, P.H., G\u00f8rtz, I.L.: Compressed subsequence matching and packed tree coloring. Algorithmica 77, 336\u2013348 (2017)","journal-title":"Algorithmica"},{"key":"523_CR16","doi-asserted-by":"crossref","unstructured":"Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Absent subsequences in words. In: International Conference on Reachability Problems, 115\u2013131 (2021). Springer","DOI":"10.1007\/978-3-030-89716-1_8"},{"key":"523_CR17","doi-asserted-by":"crossref","unstructured":"Tronicek, Z.: On problems related to absent subsequences. In: International Conference on Combinatorial Optimization and Applications (COCOA), 351\u2013363 (2023). Springer","DOI":"10.1007\/978-3-031-49614-1_26"},{"key":"523_CR18","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2023.106398","volume":"182","author":"H Bannai","year":"2023","unstructured":"Bannai, H., Tomohiro, I., K\u00f6ppl, D.: Longest bordered and periodic subsequences. Inf. Process. Lett. 182, 106398 (2023)","journal-title":"Inf. Process. Lett."},{"key":"523_CR19","doi-asserted-by":"crossref","unstructured":"Bannai, H., I, T., Kociumaka, T., K\u00f6ppl, D., Puglisi, S.J.: Computing longest Lyndon subsequences and longest common Lyndon subsequences. Algorithmica 86(3), 735\u2013756 (2024)","DOI":"10.1007\/s00453-023-01125-z"},{"key":"523_CR20","doi-asserted-by":"crossref","unstructured":"Das, G., Fleischer, R., Gasieniec, L., Gunopulos, D., K\u00e4rkk\u00e4inen, J.: Episode matching. In: Annual Symposium on Combinatorial Pattern Matching (CPM), 12\u201327 (1997). Springer","DOI":"10.1007\/3-540-63220-4_46"},{"key":"523_CR21","doi-asserted-by":"crossref","unstructured":"Tron\u00ed\u010dek, Z.: Episode matching. In: Annual Symposium on Combinatorial Pattern Matching (CPM), 2089, 143\u2013146 (2001). Springer","DOI":"10.1007\/3-540-48194-X_12"},{"issue":"2","key":"523_CR22","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/inco.2002.3143","volume":"174","author":"A Apostolico","year":"2002","unstructured":"Apostolico, A., Atallah, M.J.: Compact recognizers of episode sequences. Inf. Comput. 174(2), 180\u2013192 (2002)","journal-title":"Inf. Comput."},{"key":"523_CR23","doi-asserted-by":"crossref","unstructured":"Boasson, L., Cegielski, P., Guessarian, I., Matiyasevich, Y.: Window-accumulated subsequence matching problem is linear. In: ACM Symposium on Principles of Database Systems, 327\u2013336 (1999)","DOI":"10.1145\/303976.304008"},{"key":"523_CR24","doi-asserted-by":"crossref","unstructured":"C\u00e9gielski, P., Guessarian, I., Lifshits, Y., Matiyasevich, Y.: Window subsequence problems for compressed texts. In: International Computer Science Symposium in Russia, 127\u2013136 (2006). Springer","DOI":"10.1007\/11753728_15"},{"issue":"1","key":"523_CR25","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G Navarro","year":"2001","unstructured":"Navarro, G.: A guided tour to approximate string matching. ACM Computing Surveys (CSUR) 33(1), 31\u201388 (2001)","journal-title":"ACM Computing Surveys (CSUR)"},{"issue":"10","key":"523_CR26","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/135239.135243","volume":"35","author":"R Baeza-Yates","year":"1992","unstructured":"Baeza-Yates, R., Gonnet, G.H.: A new approach to text searching. Commun. ACM 35(10), 74\u201382 (1992)","journal-title":"Commun. ACM"},{"issue":"10","key":"523_CR27","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/135239.135244","volume":"35","author":"S Wu","year":"1992","unstructured":"Wu, S., Manber, U.: Fast text searching: allowing errors. Commun. ACM 35(10), 83\u201391 (1992)","journal-title":"Commun. ACM"},{"key":"523_CR28","unstructured":"Faro, S., Lecroq, T.: Twenty years of bit-parallelism in string matching. Festschrift for Bo\u0159ivoj Melichar, 72\u2013101 (2012)"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-026-00523-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-026-00523-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-026-00523-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T12:25:42Z","timestamp":1774268742000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-026-00523-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,25]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["523"],"URL":"https:\/\/doi.org\/10.1007\/s00236-026-00523-4","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,25]]},"assertion":[{"value":"3 August 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 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":"10"}}