{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:44:40Z","timestamp":1775054680603,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T00:00:00Z","timestamp":1641945600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T00:00:00Z","timestamp":1641945600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003382","name":"Core Research for Evolutional Science and Technology","doi-asserted-by":"publisher","award":["JPMJCR1401"],"award-info":[{"award-number":["JPMJCR1401"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["20174LF3T8"],"award-info":[{"award-number":["20174LF3T8"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,3]]},"DOI":"10.1007\/s00453-021-00898-5","type":"journal-article","created":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T00:02:41Z","timestamp":1641945761000},"page":"757-783","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Enumeration of Maximal Common Subsequences Between Two Strings"],"prefix":"10.1007","volume":"84","author":[{"given":"Alessio","family":"Conte","sequence":"first","affiliation":[]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8738-1595","authenticated-orcid":false,"given":"Giulia","family":"Punzi","sequence":"additional","affiliation":[]},{"given":"Takeaki","family":"Uno","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,12]]},"reference":[{"key":"898_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: Tight hardness results for LCS and other sequence similarity measures. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 59\u201378 (2015)","DOI":"10.1109\/FOCS.2015.14"},{"key":"898_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 434\u2013443. IEEE (2014)","DOI":"10.1109\/FOCS.2014.53"},{"issue":"2","key":"898_CR3","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0020-0190(86)90044-X","volume":"23","author":"A Apostolico","year":"1986","unstructured":"Apostolico, A.: Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings. Inf. Process. Lett. 23(2), 63\u201369 (1986)","journal-title":"Inf. Process. Lett."},{"key":"898_CR4","unstructured":"Bergroth, L., Hakonen, H., Raita, T.: A survey of longest common subsequence algorithms. In: Proceedings 7th International Symposium on String Processing and Information Retrieval, pp. 39\u201348. SPIRE (2000)"},{"issue":"2","key":"898_CR5","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1093\/bib\/4.2.105","volume":"4","author":"P Chain","year":"2003","unstructured":"Chain, P., Kurtz, S., Ohlebusch, E., Slezak, T.: An applications-focused review of comparative genomics tools: capabilities, limitations and future challenges. Brief. Bioinf. 4(2), 105\u2013123 (2003)","journal-title":"Brief. Bioinf."},{"key":"898_CR6","doi-asserted-by":"crossref","unstructured":"Conte, A., Grossi, R., Punzi, G., Uno, T.: Polynomial-delay enumeration of maximal common subsequences. In: Brisaboa, N.R., Puglisi, S.J. (eds.) String Processing and Information Retrieval, pp. 189\u2013202. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-32686-9_14"},{"issue":"3\u20134","key":"898_CR7","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\u0131\u010dek, Z.: Directed acyclic subsequence graph-overview. J. Discrete Algorithms 1(3\u20134), 255\u2013280 (2003)","journal-title":"J. Discrete Algorithms"},{"issue":"11","key":"898_CR8","doi-asserted-by":"publisher","first-page":"2369","DOI":"10.1093\/nar\/27.11.2369","volume":"27","author":"AL Delcher","year":"1999","unstructured":"Delcher, A.L., Kasif, S., Fleischmann, R.D., Peterson, J., White, O., Salzberg, S.L.: Alignment of whole genomes. Nucl. Acids Res. 27(11), 2369\u20132376 (1999)","journal-title":"Nucl. Acids Res."},{"issue":"2","key":"898_CR9","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1006\/inco.1996.0011","volume":"124","author":"CB Fraser","year":"1996","unstructured":"Fraser, C.B., Irving, R.W., Middendorf, M.: Maximal common subsequences and minimal common supersequences. Inf. Comput. 124(2), 145\u2013153 (1996)","journal-title":"Inf. Comput."},{"issue":"4","key":"898_CR10","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"DS Hirschberg","year":"1977","unstructured":"Hirschberg, D.S.: Algorithms for the longest common subsequence problem. J. ACM 24(4), 664\u2013675 (1977)","journal-title":"J. ACM"},{"issue":"1","key":"898_CR11","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF01934514","volume":"24","author":"WJ Hsu","year":"1984","unstructured":"Hsu, W.J., Du, M.W.: Computing a longest common subsequence for a set of strings. BIT Numer. Math. 24(1), 45\u201359 (1984)","journal-title":"BIT Numer. Math."},{"issue":"5","key":"898_CR12","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"},{"issue":"2","key":"898_CR13","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)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"898_CR14","doi-asserted-by":"publisher","first-page":"1916","DOI":"10.1137\/120862612","volume":"28","author":"MM Kant\u00e9","year":"2014","unstructured":"Kant\u00e9, M.M., Limouzy, V., Mary, A., Nourine, L.: On the enumeration of minimal dominating sets and related notions. SIAM J. Discrete Math. 28(4), 1916\u20131929 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"898_CR15","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume 3: Sorting and Searching of Addison-Wesley series in computer science and information processing. Addison-Wesley (1997)"},{"issue":"2","key":"898_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/gb-2004-5-2-r12","volume":"5","author":"S Kurtz","year":"2004","unstructured":"Kurtz, S., Phillippy, A., Delcher, A.L., Smoot, M., Shumway, M., Antonescu, C., Salzberg, S.L.: Versatile and open software for comparing large genomes. Genome Biol. 5(2), 1\u20139 (2004)","journal-title":"Genome Biol."},{"issue":"3","key":"898_CR17","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1137\/0209042","volume":"9","author":"EL Lawler","year":"1980","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM J. Comput. 9(3), 558\u2013565 (1980)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"898_CR18","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. Sc. 20(1), 18\u201331 (1980)","journal-title":"J. Comput. Syst. Sc."},{"key":"898_CR19","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding $$k$$-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43-es (2007)","DOI":"10.1145\/1290672.1290680"},{"key":"898_CR20","unstructured":"Sakai, Y.: Maximal common subsequence algorithms. In: Navarro, G., Sankoff, D., Zhu, B. (eds.) Annual Symposium on Combinatorial Pattern Matching (CPM 2018), Volume 105 of Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, pp. 1:1\u20131:10. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2018)"},{"key":"898_CR21","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.tcs.2019.06.020","volume":"793","author":"Y Sakai","year":"2019","unstructured":"Sakai, Y.: Maximal common subsequence algorithms. Theor. Comput. Sci. 793, 132\u2013139 (2019)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"898_CR22","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)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00898-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00898-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00898-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,15]],"date-time":"2022-03-15T09:05:30Z","timestamp":1647335130000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00898-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,12]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["898"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00898-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,12]]},"assertion":[{"value":"31 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}