{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T22:29:26Z","timestamp":1772058566275,"version":"3.50.1"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031929342","type":"print"},{"value":"9783031929359","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-92935-9_9","type":"book-chapter","created":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T04:07:21Z","timestamp":1747454841000},"page":"136-150","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Subsequence Matching and\u00a0LCS with\u00a0Segment Number Constraints"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-5330-7256","authenticated-orcid":false,"given":"Yuki","family":"Yonemoto","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2922-9434","authenticated-orcid":false,"given":"Takuya","family":"Mieno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1833-010X","authenticated-orcid":false,"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5175-465X","authenticated-orcid":false,"given":"Ryo","family":"Yoshinaka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4978-8316","authenticated-orcid":false,"given":"Ayumi","family":"Shinohara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,18]]},"reference":[{"key":"9_CR1","doi-asserted-by":"publisher","unstructured":"Banerjee, A., Gibney, D., Thankachan, S.V.: Longest common substring with gaps and related problems. In: ESA 2024. LIPIcs, vol.\u00a0308, pp. 16:1\u201316:18 (2024). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2024.16","DOI":"10.4230\/LIPICS.ESA.2024.16"},{"key":"9_CR2","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: 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022. LIPIcs, vol.\u00a0223, pp. 4:1\u20134:12 (2022). https:\/\/doi.org\/10.4230\/LIPICS.CPM.2022.4","DOI":"10.4230\/LIPICS.CPM.2022.4"},{"key":"9_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546853","author":"M Crochemore","year":"2007","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings (2007). https:\/\/doi.org\/10.1017\/CBO9780511546853","journal-title":"Algorithms on Strings"},{"issue":"3","key":"9_CR4","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1145\/116825.116845","volume":"38","author":"M Crochemore","year":"1991","unstructured":"Crochemore, M., Perrin, D.: Two-way string matching. J. ACM 38(3), 651\u2013675 (1991). https:\/\/doi.org\/10.1145\/116825.116845","journal-title":"J. ACM"},{"key":"9_CR5","doi-asserted-by":"publisher","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, Miami Beach, Florida, USA, October 19-22, 1997, pp. 137\u2013143. IEEE Computer Society (1997). https:\/\/doi.org\/10.1109\/SFCS.1997.646102","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"3","key":"9_CR6","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1016\/0022-0000(83)90002-8","volume":"26","author":"Z Galil","year":"1983","unstructured":"Galil, Z., Seiferas, J.I.: Time-space-optimal string matching. J. Comput. Syst. Sci. 26(3), 280\u2013294 (1983). https:\/\/doi.org\/10.1016\/0022-0000(83)90002-8","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9_CR7","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1109\/TCBB.2008.116","volume":"5","author":"R Giancarlo","year":"2008","unstructured":"Giancarlo, R., Hannenhalli, S.: Guest editors\u2019 introduction to the special section on algorithms in bioinformatics. IEEE ACM Trans. Comput. Biol. Bioinform. 5(4), 482\u2013483 (2008). https:\/\/doi.org\/10.1109\/TCBB.2008.116","journal-title":"IEEE ACM Trans. Comput. Biol. Bioinform."},{"issue":"3","key":"9_CR8","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O Gotoh","year":"1982","unstructured":"Gotoh, O.: An improved algorithm for matching biological sequences. J. Mol. Biol. 162(3), 705\u2013708 (1982). https:\/\/doi.org\/10.1016\/0022-2836(82)90398-9","journal-title":"J. Mol. Biol."},{"key":"9_CR9","doi-asserted-by":"publisher","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997). https:\/\/doi.org\/10.1017\/CBO9780511574931","DOI":"10.1017\/CBO9780511574931"},{"issue":"2","key":"9_CR10","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984). https:\/\/doi.org\/10.1137\/0213024","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9_CR11","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Jr., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977). https:\/\/doi.org\/10.1137\/0206024","journal-title":"SIAM J. Comput."},{"key":"9_CR12","doi-asserted-by":"publisher","unstructured":"Li, T., Jiang, H., Wang, L., Zhu, D.: Longest (k]-tuple common substrings. In: Li, B., Li, M., Sun, X. (eds.) Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Hong Kong SAR, China, July 29-31, 2024, Proceedings. Lecture Notes in Computer Science, vol. 14752, pp. 106\u2013114. Springer (2024). https:\/\/doi.org\/10.1007\/978-981-97-7752-5_8","DOI":"10.1007\/978-981-97-7752-5_8"},{"key":"9_CR13","doi-asserted-by":"publisher","unstructured":"Li, T., Zhu, D., Jiang, H., Feng, H., Cui, X.: Longest $$k$$-tuple common sub-strings. In: Adjeroh, D.A., (eds.) et al. IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2022, pp. 63\u201366. IEEE (2022). https:\/\/doi.org\/10.1109\/BIBM55620.2022.9995199","DOI":"10.1109\/BIBM55620.2022.9995199"},{"key":"9_CR14","doi-asserted-by":"publisher","unstructured":"Manea, F., Richardsen, J., Schmid, M.L.: Subsequences with generalised gap constraints: upper and lower complexity bounds. In: Inenaga, S., Puglisi, S.J. (eds.) 35th Annual Symposium on Combinatorial Pattern Matching, CPM 2024, June 25-27, 2024, Fukuoka, Japan. LIPIcs, vol.\u00a0296, pp. 22:1\u201322:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPICS.CPM.2024.22","DOI":"10.4230\/LIPICS.CPM.2024.22"},{"key":"9_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 Informatica 18, 171\u2013179 (1982). https:\/\/doi.org\/10.1007\/BF00264437","journal-title":"Acta Informatica"},{"issue":"1","key":"9_CR16","doi-asserted-by":"publisher","first-page":"40","DOI":"10.3390\/A4010040","volume":"4","author":"D Shapira","year":"2011","unstructured":"Shapira, D., Storer, J.A.: Edit distance with block deletions. Algorithms 4(1), 40\u201360 (2011). https:\/\/doi.org\/10.3390\/A4010040","journal-title":"Algorithms"},{"issue":"1","key":"9_CR17","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T Smith","year":"1981","unstructured":"Smith, T., Waterman, M.: Identification of common molecular subsequences. J. Mol. Biol. 147(1), 195\u2013197 (1981). https:\/\/doi.org\/10.1016\/0022-2836(81)90087-5","journal-title":"J. Mol. Biol."},{"issue":"1","key":"9_CR18","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"RA Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. J. ACM 21(1), 168\u2013173 (1974). https:\/\/doi.org\/10.1145\/321796.321811","journal-title":"J. ACM"},{"key":"9_CR19","doi-asserted-by":"publisher","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973, pp. 1\u201311. IEEE Computer Society (1973). https:\/\/doi.org\/10.1109\/SWAT.1973.13","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-92935-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T00:37:23Z","timestamp":1762907843000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-92935-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031929342","9783031929359"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-92935-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"18 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rome","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/easyconferences.eu\/ciac2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}