{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T15:34:40Z","timestamp":1743089680608,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030250041"},{"type":"electronic","value":"9783030250058"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-25005-8_7","type":"book-chapter","created":{"date-parts":[[2019,7,14]],"date-time":"2019-07-14T23:02:23Z","timestamp":1563145343000},"page":"70-84","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Finding Periods in Cartesian Tree Matching"],"prefix":"10.1007","author":[{"given":"Magsarjav","family":"Bataa","sequence":"first","affiliation":[]},{"given":"Sung Gwan","family":"Park","sequence":"additional","affiliation":[]},{"given":"Amihood","family":"Amir","sequence":"additional","affiliation":[]},{"given":"Gad M.","family":"Landau","sequence":"additional","affiliation":[]},{"given":"Kunsoo","family":"Park","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,7,10]]},"reference":[{"issue":"5","key":"7_CR1","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0020-0190(95)00111-O","volume":"55","author":"Tatsuya Akutsu","year":"1995","unstructured":"Akutsu, T.: Approximate string matching with don\u2019t care characters. Inf. Process. Lett. 55(5), 235\u2013239 (1995). https:\/\/doi.org\/10.1016\/0020-0190(95)00111-O","journal-title":"Information Processing Letters"},{"key":"7_CR2","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/j.tcs.2016.04.030","volume":"656","author":"Amihood Amir","year":"2016","unstructured":"Amir, A., Apostolico, A., Hirst, T., Landau, G.M., Lewenstein, N., Rozenberg, L.: Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings. Theoret. Comput. Sci. 656, 146\u2013159 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2016.04.030","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"7_CR3","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1006\/jagm.2000.1120","volume":"37","author":"Amihood Amir","year":"2000","unstructured":"Amir, A., Aumann, Y., Landau, G.M., Lewenstein, M., Lewenstein, N.: Pattern matching with swaps. J. Algorithms 37(2), 247\u2013266 (2000). https:\/\/doi.org\/10.1006\/jagm.2000.1120","journal-title":"Journal of Algorithms"},{"issue":"3","key":"7_CR4","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0020-0190(94)90086-8","volume":"49","author":"Amihood Amir","year":"1994","unstructured":"Amir, A., Farach, M., Muthukrishnan, S.: Alphabet dependence in parameterized matching. Inf. Process. Lett. 49(3), 111\u2013115 (1994). https:\/\/doi.org\/10.1016\/0020-0190(94)90086-8","journal-title":"Information Processing Letters"},{"issue":"1","key":"7_CR5","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/S0020-0190(01)00302-7","volume":"83","author":"Amihood Amir","year":"2002","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Approximate swapped matching. Inf. Process. Lett. 83(1), 33\u201339 (2002). https:\/\/doi.org\/10.1016\/S0020-0190(01)00302-7","journal-title":"Information Processing Letters"},{"issue":"1","key":"7_CR6","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.jda.2006.03.014","volume":"5","author":"Alberto Apostolico","year":"2007","unstructured":"Apostolico, A., Erdos, P.L., Lewenstein, M.: Parameterized matching with mismatches. J. Discrete Algorithms 5(1), 135\u2013140 (2007). https:\/\/doi.org\/10.1016\/j.jda.2006.03.014","journal-title":"Journal of Discrete Algorithms"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Baker, B.S.: A theory of parameterized pattern matching: algorithms and applications. In: STOC, pp. 71\u201380 (1993). https:\/\/doi.org\/10.1145\/167088.167115","DOI":"10.1145\/167088.167115"},{"key":"7_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-45278-9_5","volume-title":"Combinatorial Algorithms","author":"W Bland","year":"2013","unstructured":"Bland, W., Kucherov, G., Smyth, W.F.: Prefix table construction and conversion. In: Lecroq, T., Mouchard, L. (eds.) IWOCA 2013. LNCS, vol. 8288, pp. 41\u201353. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-45278-9_5"},{"issue":"02","key":"7_CR9","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1142\/S0129054112400175","volume":"23","author":"P\u00c9TER BURCSI","year":"2012","unstructured":"Burcsi, P., Cicalese, F., Fici, G., Liptak, Z.: Algorithms for jumbled pattern matching in strings. Int. J. Found. Comput. Sci. 23(2), 357\u2013374 (2012). https:\/\/doi.org\/10.1142\/S0129054112400175","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"1","key":"7_CR10","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s00224-011-9344-5","volume":"50","author":"P\u00e9ter Burcsi","year":"2011","unstructured":"Burcsi, P., Cicalese, F., Fici, G., Liptak, Z.: On approximate jumbled pattern matching in strings. Theory Comput. Syst. 50(1), 35\u201351 (2012). https:\/\/doi.org\/10.1007\/s00224-011-9344-5","journal-title":"Theory of Computing Systems"},{"key":"7_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-319-23826-5_18","volume-title":"String Processing and Information Retrieval","author":"T Chhabra","year":"2015","unstructured":"Chhabra, T., Giaquinta, E., Tarhio, J.: Filtration algorithms for approximate order-preserving matching. In: Iliopoulos, C., Puglisi, S., Yilmaz, E. (eds.) SPIRE 2015. LNCS, vol. 9309, pp. 177\u2013187. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-23826-5_18"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: STOC, pp. 91\u2013100 (2004). https:\/\/doi.org\/10.1145\/1007352.1007374","DOI":"10.1145\/1007352.1007374"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.tcs.2015.06.050","volume":"638","author":"Maxime Crochemore","year":"2016","unstructured":"Crochemore, M., et al.: Order-preserving indexing. Theoret. Comput. Sci. 638, 122\u2013135 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2015.06.050","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"7_CR14","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.ipl.2012.11.001","volume":"113","author":"M. Crochemore","year":"2013","unstructured":"Crochemore, M., et al.: A note on efficient computation of all Abelian periods in a string. Inf. Process. Lett. 113(3), 74\u201377 (2013). https:\/\/doi.org\/10.1016\/j.ipl.2012.11.001","journal-title":"Information Processing Letters"},{"key":"7_CR15","unstructured":"Fischer, M.J., Paterson, M.S.: String-matching and other products. Technical report, MIT Cambridge Project MAC (1974)"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: STOC, pp. 135\u2013143 (1984). https:\/\/doi.org\/10.1145\/800057.808675","DOI":"10.1145\/800057.808675"},{"key":"7_CR17","unstructured":"Gourdel, G., Kociumaka, T., Radoszewski, J., Rytter, W., Shur, A.M., Walen, T.: String periods in the order-preserving model. In: STACS, pp. 38:1\u201338:16 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2018.38"},{"key":"7_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/978-3-540-77566-9_27","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"CS Iliopoulos","year":"2008","unstructured":"Iliopoulos, C.S., Rahman, M.S.: A new model to solve the swap matching problem and efficient algorithms for short patterns. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol. 4910, pp. 316\u2013327. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-77566-9_27"},{"key":"7_CR19","unstructured":"Kalai, A.: Efficient pattern-matching with don\u2019t cares. In: SODA, pp. 655\u2013656 (2002)"},{"issue":"2","key":"7_CR20","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s11786-016-0282-0","volume":"11","author":"Jinil Kim","year":"2017","unstructured":"Kim, J., Amir, A., Na, J.C., Park, K., Sim, J.S.: On representations of ternary order relations in numeric strings. Math. Comput. Sci. 11(2), 127\u2013136 (2017). https:\/\/doi.org\/10.1007\/s11786-016-0282-0","journal-title":"Mathematics in Computer Science"},{"key":"7_CR21","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.tcs.2013.10.006","volume":"525","author":"Jinil Kim","year":"2014","unstructured":"Kim, J., et al.: Order-preserving matching. Theoret. Comput. Sci. 525, 68\u201379 (2014). https:\/\/doi.org\/10.1016\/j.tcs.2013.10.006","journal-title":"Theoretical Computer Science"},{"key":"7_CR22","doi-asserted-by":"crossref","unstructured":"Knuth, D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977). https:\/\/doi.org\/10.1137\/0206024","DOI":"10.1137\/0206024"},{"key":"7_CR23","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/j.jcss.2016.09.003","volume":"84","author":"T. Kociumaka","year":"2017","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W.: Fast algorithms for Abelian periods in words and greatest common divisor queries. J. Comput. Syst. Sci. 84, 205\u2013218 (2017). https:\/\/doi.org\/10.1016\/j.jcss.2016.09.003","journal-title":"Journal of Computer and System Sciences"},{"issue":"12","key":"7_CR24","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). https:\/\/doi.org\/10.1016\/j.ipl.2013.03.015","journal-title":"Information Processing Letters"},{"key":"7_CR25","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.tcs.2016.02.017","volume":"656","author":"Yoshiaki Matsuoka","year":"2016","unstructured":"Matsuoka, Y., Aoki, T., Inenaga, S., Bannai, H., Takeda, M.: Generalized pattern matching and periodicity under substring consistent equivalence relations. Theoret. Comput. Sci. 656, 225\u2013233 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2016.02.017","journal-title":"Theoretical Computer Science"},{"key":"7_CR26","unstructured":"Park, S.G., Amir, A., Landau, G.M., Park, K.: Cartesian tree matching and indexing. Accepted to CPM (2019). https:\/\/arxiv.org\/abs\/1905.08974"},{"key":"7_CR27","unstructured":"Sorenson, J.: An introduction to prime number sieves. Technical report, Department of Computer Sciences, University of Wisconsin-Madison (1990)"},{"key":"7_CR28","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/BFb0030787","volume-title":"Combinatorial Pattern Matching","author":"Jens Stoye","year":"1998","unstructured":"Stoye, J., Gusfield, D.: Simple and flexible detection of contiguous repeats using a suffix tree. Theoret. Comput. Sci. 270(1), 843\u2013856 (2002). https:\/\/doi.org\/10.1007\/bfb0030787"},{"issue":"4","key":"7_CR29","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"Jean Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A unifying look at data structures. Commun. ACM 23(4), 229\u2013239 (1980). https:\/\/doi.org\/10.1145\/358841.358852","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-25005-8_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T17:12:55Z","timestamp":1710349975000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-25005-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030250041","9783030250058"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-25005-8_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"10 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Pisa","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":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/iwoca2019.di.unipi.it\/","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":"73","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":"36","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":"0","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":"49% - 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","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":"5-6","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":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}