{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:56:11Z","timestamp":1758272171921,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030866914"},{"type":"electronic","value":"9783030866921"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-86692-1_3","type":"book-chapter","created":{"date-parts":[[2021,9,27]],"date-time":"2021-09-27T21:24:41Z","timestamp":1632777881000},"page":"21-32","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Longest Common Rollercoasters"],"prefix":"10.1007","author":[{"given":"Kosuke","family":"Fujita","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6269-9353","authenticated-orcid":false,"given":"Yuto","family":"Nakashima","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1833-010X","authenticated-orcid":false,"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6856-5185","authenticated-orcid":false,"given":"Hideo","family":"Bannai","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6138-1607","authenticated-orcid":false,"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,27]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: Tight hardness results for LCS and other sequence similarity measures. In: Guruswami, V. (ed.) IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17\u201320 October 2015, pp. 59\u201378. IEEE Computer Society (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.14","DOI":"10.1109\/FOCS.2015.14"},{"key":"3_CR2","doi-asserted-by":"publisher","unstructured":"Agrawal, A., Gawrychowski, P.: A faster subquadratic algorithm for the longest common increasing subsequence problem. In: Cao, Y., Cheng, S., Li, M. (eds.) 31st International Symposium on Algorithms and Computation, ISAAC 2020, 14\u201318 December 2020, Hong Kong, China (Virtual Conference). LIPIcs, vol. 181, pp. 4:1\u20134:12. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2020.4","DOI":"10.4230\/LIPIcs.ISAAC.2020.4"},{"key":"3_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/978-3-030-00479-8_4","volume-title":"String Processing and Information Retrieval","author":"LAK Ayad","year":"2018","unstructured":"Ayad, L.A.K., et al.: Longest property-preserved common factor. In: Gagie, T., Moffat, A., Navarro, G., Cuadros-Vargas, E. (eds.) SPIRE 2018. LNCS, vol. 11147, pp. 42\u201349. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-00479-8_4"},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/j.tcs.2020.02.012","volume":"812","author":"LAK Ayad","year":"2020","unstructured":"Ayad, L.A.K., et al.: Longest property-preserved common factor: a new string-processing framework. Theor. Comput. Sci. 812, 244\u2013251 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2020.02.012","journal-title":"Theor. Comput. Sci."},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.tcs.2017.02.018","volume":"710","author":"SW Bae","year":"2018","unstructured":"Bae, S.W., Lee, I.: On finding a longest common palindromic subsequence. Theor. Comput. Sci. 710, 29\u201334 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2017.02.018","journal-title":"Theor. Comput. Sci."},{"key":"3_CR6","doi-asserted-by":"publisher","unstructured":"Biedl, T.C., et al.: Rollercoasters and caterpillars. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, 9\u201313 July 2018, Prague, Czech Republic. LIPIcs, vol. 107, pp. 18:1\u201318:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.18","DOI":"10.4230\/LIPIcs.ICALP.2018.18"},{"issue":"2","key":"3_CR7","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/18M1192226","volume":"33","author":"TC Biedl","year":"2019","unstructured":"Biedl, T.C., et al.: Rollercoasters: long sequences without short runs. SIAM J. Discret. Math. 33(2), 845\u2013861 (2019). https:\/\/doi.org\/10.1137\/18M1192226","journal-title":"SIAM J. Discret. Math."},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-319-73915-1_24","volume-title":"Graph Drawing and Network Visualization","author":"T Biedl","year":"2018","unstructured":"Biedl, T., Chan, T.M., Derka, M., Jain, K., Lubiw, A.: Improved bounds for drawing trees on fixed points with L-shaped edges. In: Frati, F., Ma, K.-L. (eds.) GD 2017. LNCS, vol. 10692, pp. 305\u2013317. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-73915-1_24"},{"issue":"3","key":"3_CR9","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s10878-006-9031-7","volume":"13","author":"W Chan","year":"2007","unstructured":"Chan, W., Zhang, Y., Fung, S.P.Y., Ye, D., Zhu, H.: Efficient algorithms for finding a longest common increasing subsequence. J. Comb. Optim. 13(3), 277\u2013288 (2007). https:\/\/doi.org\/10.1007\/s10878-006-9031-7","journal-title":"J. Comb. Optim."},{"issue":"3","key":"3_CR10","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17(3), 427\u2013462 (1988). https:\/\/doi.org\/10.1137\/0217026","journal-title":"SIAM J. Comput."},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-642-35926-2_24","volume-title":"Combinatorial Algorithms","author":"SR Chowdhury","year":"2012","unstructured":"Chowdhury, S.R., Hasan, M.M., Iqbal, S., Rahman, M.S.: Computing a longest common palindromic subsequence. In: Arumugam, S., Smyth, W.F. (eds.) IWOCA 2012. LNCS, vol. 7643, pp. 219\u2013223. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-35926-2_24"},{"issue":"4","key":"3_CR12","doi-asserted-by":"publisher","first-page":"329","DOI":"10.3233\/FI-2014-974","volume":"129","author":"SR Chowdhury","year":"2014","unstructured":"Chowdhury, S.R., Hasan, M.M., Iqbal, S., Rahman, M.S.: Computing a longest common palindromic subsequence. Fundam. Inform. 129(4), 329\u2013340 (2014). https:\/\/doi.org\/10.3233\/FI-2014-974","journal-title":"Fundam. Inform."},{"key":"3_CR13","doi-asserted-by":"publisher","unstructured":"Duraj, L.: A sub-quadratic algorithm for the longest common increasing subsequence problem. In: Paul, C., Bl\u00e4ser, M. (eds.) 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, 10\u201313 March 2020, Montpellier, France. LIPIcs, vol. 154, pp. 41:1\u201341:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.41","DOI":"10.4230\/LIPIcs.STACS.2020.41"},{"key":"3_CR14","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Manea, F., Serafin, R.: Fast and longest rollercoasters. In: Niedermeier, R., Paul, C. (eds.) 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, 13\u201316 March 2019, Berlin, Germany. LIPIcs, vol. 126, pp. 30:1\u201330:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.30","DOI":"10.4230\/LIPIcs.STACS.2019.30"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.ipl.2017.08.006","volume":"129","author":"S Inenaga","year":"2018","unstructured":"Inenaga, S., Hyyr\u00f6, H.: A hardness result and new algorithm for the longest common palindromic subsequence problem. Inf. Process. Lett. 129, 11\u201315 (2018). https:\/\/doi.org\/10.1016\/j.ipl.2017.08.006","journal-title":"Inf. Process. Lett."},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-030-59212-7_11","volume-title":"String Processing and Information Retrieval","author":"T Inoue","year":"2020","unstructured":"Inoue, T., Inenaga, S., Bannai, H.: Longest square subsequence problem revisited. In: Boucher, C., Thankachan, S.V. (eds.) SPIRE 2020. LNCS, vol. 12303, pp. 147\u2013154. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-59212-7_11"},{"key":"3_CR17","doi-asserted-by":"publisher","unstructured":"Inoue, T., Inenaga, S., Hyyr\u00f6, H., Bannai, H., Takeda, M.: Computing longest common square subsequences. In: Navarro, G., Sankoff, D., Zhu, B. (eds.) Annual Symposium on Combinatorial Pattern Matching, CPM 2018, 2\u20134 July 2018, Qingdao, China. LIPIcs, vol. 105, pp. 15:1\u201315:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2018.15","DOI":"10.4230\/LIPIcs.CPM.2018.15"},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-030-32686-9_12","volume-title":"String Processing and Information Retrieval","author":"K Kai","year":"2019","unstructured":"Kai, K., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M., Kociumaka, T.: On longest common property preserved substring queries. In: Brisaboa, N.R., Puglisi, S.J. (eds.) SPIRE 2019. LNCS, vol. 11811, pp. 162\u2013174. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-32686-9_12"},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-540-30213-1_13","volume-title":"String Processing and Information Retrieval","author":"A Kosowski","year":"2004","unstructured":"Kosowski, A.: An efficient algorithm for the longest tandem scattered subsequence problem. In: Apostolico, A., Melucci, M. (eds.) SPIRE 2004. LNCS, vol. 3246, pp. 93\u2013100. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30213-1_13"},{"issue":"4","key":"3_CR20","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/j.jda.2011.03.013","volume":"9","author":"M Kutz","year":"2011","unstructured":"Kutz, M., Brodal, G.S., Kaligosi, K., Katriel, I.: Faster algorithms for computing longest common increasing subsequences. J. Discrete Algorithms 9(4), 314\u2013325 (2011). https:\/\/doi.org\/10.1016\/j.jda.2011.03.013","journal-title":"J. Discrete Algorithms"},{"key":"3_CR21","unstructured":"Russo, L.M.S., Francisco, A.P.: Small longest tandem scattered subsequences. CoRR abs\/2006.14029 (2020). https:\/\/arxiv.org\/abs\/2006.14029"},{"issue":"4","key":"3_CR22","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/s11786-007-0033-3","volume":"1","author":"A Tiskin","year":"2008","unstructured":"Tiskin, A.: Semi-local string comparison: algorithmic techniques and applications. Math. Comput. Sci. 1(4), 571\u2013603 (2008). https:\/\/doi.org\/10.1007\/s11786-007-0033-3","journal-title":"Math. Comput. Sci."},{"issue":"5","key":"3_CR23","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.ipl.2004.10.014","volume":"93","author":"I Yang","year":"2005","unstructured":"Yang, I., Huang, C., Chao, K.: A fast algorithm for computing a longest common increasing subsequence. Inf. Process. Lett. 93(5), 249\u2013253 (2005). https:\/\/doi.org\/10.1016\/j.ipl.2004.10.014","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-86692-1_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,27]],"date-time":"2021-09-27T21:25:43Z","timestamp":1632777943000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-86692-1_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030866914","9783030866921"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-86692-1_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"27 September 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lille","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 October 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 October 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cristal.univ-lille.fr\/spire2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"14","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.87","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.32","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2 invited papers are also included. The symposium was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}