{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T08:06:28Z","timestamp":1787731588652,"version":"build-2784847793"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030004781","type":"print"},{"value":"9783030004798","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[[2018]]},"DOI":"10.1007\/978-3-030-00479-8_20","type":"book-chapter","created":{"date-parts":[[2018,9,13]],"date-time":"2018-09-13T14:58:18Z","timestamp":1536850698000},"page":"241-253","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Searching for a Modified Pattern in a Changing Text"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eitan","family":"Kondratovsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,9,14]]},"reference":[{"key":"20_CR1","unstructured":"The new oxford english dictionary. http:\/\/db.uwaterloo.ca\/OED"},{"key":"20_CR2","unstructured":"The responsa project. http:\/\/www.biu.ac.il\/JH\/Responsa\/"},{"key":"20_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-78909-5","volume-title":"The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching","author":"D Adjeroh","year":"2008","unstructured":"Adjeroh, D., Bell, T., Mukherjee, A.: The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching. Springer, Boston (2008). https:\/\/doi.org\/10.1007\/978-0-387-78909-5. ISBN 00387789081"},{"key":"20_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-3-319-67428-5_2","volume-title":"String Processing and Information Retrieval","author":"A Amir","year":"2017","unstructured":"Amir, A., Charalampopoulos, P., Iliopoulos, C.S., Pissis, S.P., Radoszewski, J.: Longest common factor after one edit operation. In: Fici, G., Sciortino, M., Venturini, R. (eds.) SPIRE 2017. LNCS, vol. 10508, pp. 14\u201326. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-67428-5_2"},{"key":"20_CR5","unstructured":"Amir, A., Charalampopoulos, P., Pissis, S.P., Radoszewski, J.: Longest common factor made fully dynamic. CoRR, abs\/1804.08731 (2018)"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/11575832_9","volume-title":"String Processing and Information Retrieval","author":"A Amir","year":"2005","unstructured":"Amir, A., Kopelowitz, T., Lewenstein, M., Lewenstein, N.: Towards real-time suffix tree construction. In: Consens, M., Navarro, G. (eds.) SPIRE 2005. LNCS, vol. 3772, pp. 67\u201378. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11575832_9"},{"issue":"2","key":"20_CR7","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/1240233.1240242","volume":"3","author":"A Amir","year":"2007","unstructured":"Amir, A., Landau, G.M., Lewenstein, M., Sokol, D.: Dynamic text and static pattern matching. ACM Trans. Algorithms 3(2), 19 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"20_CR8","unstructured":"Amir, A., Nor, I.: Real-time indexing over fixed finite alphabets. In: Proceedings of 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1086\u20131095 (2008)"},{"key":"20_CR9","volume-title":"Computer Algorithms: String Pattern Matching Strategies (Practitioners)","author":"J Aoe","year":"1994","unstructured":"Aoe, J.: Computer Algorithms: String Pattern Matching Strategies (Practitioners). Wiley Blackwell, London (1994). ISBN 0818654627"},{"issue":"4","key":"20_CR10","first-page":"464","volume":"16","author":"P Bille","year":"2017","unstructured":"Bille, P., et al.: Dynamic relative compression, dynamic partial sums, and substring concatenation. Algorithmica 16(4), 464\u2013497 (2017)","journal-title":"Algorithmica"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.jda.2012.07.003","volume":"18","author":"D Breslauer","year":"2013","unstructured":"Breslauer, D., Italiano, G.F.: Near real-time suffix tree construction via the fringe marked ancestor problem. J. Discret. Algorithms 18, 32\u201348 (2013)","journal-title":"J. Discret. Algorithms"},{"key":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/3-540-45253-2_12","volume-title":"Algorithms - ESA 2000","author":"AL Buchsbaum","year":"2000","unstructured":"Buchsbaum, A.L., Goodrich, M.T., Westbrook, J.R.: Range searching over tree cross products. In: Paterson, M.S. (ed.) ESA 2000. LNCS, vol. 1879, pp. 120\u2013131. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-45253-2_12"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1137\/1.9781611973068.85","volume-title":"Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Rapha\u00ebl Clifford","year":"2009","unstructured":"Clifford, R., Efremenko, K., Porat, E., Rothschild, A.: From coding theory to efficient pattern matching. In: Proceedings of 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 778\u2013784 (2009)"},{"issue":"1","key":"20_CR14","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1137\/S0097539701424465","volume":"33","author":"R Cole","year":"2003","unstructured":"Cole, R., Hariharan, R.: Faster suffix tree construction with missing suffix links. SIAM J. Comput. 33(1), 26\u201342 (2003)","journal-title":"SIAM J. Comput."},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: Proceedings of 38th IEEE Symposium on Foundations of Computer Science, pp. 137\u2013143 (1997)","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"2","key":"20_CR16","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1006\/jagm.1996.0814","volume":"22","author":"P Ferragina","year":"1997","unstructured":"Ferragina, P.: Dynamic text indexing under string updates. J. Algorithms 22(2), 296\u2013328 (1997)","journal-title":"J. Algorithms"},{"issue":"3","key":"20_CR17","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/S0097539795286119","volume":"27","author":"P Ferragina","year":"1998","unstructured":"Ferragina, P., Grossi, R.: Optimal on-line search and sublinear time update in string matching. SIAM J. Comput. 27(3), 713\u2013736 (1998)","journal-title":"SIAM J. Comput."},{"key":"20_CR18","unstructured":"Gawrychowski, P., Karczmarz, A., Kociumaka, T., Lacki, J., Sankowski, P.: Optimal dynamic strings. CoRR, abs\/1511.02612 (2015)"},{"key":"20_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-3-662-44777-2_38","volume-title":"Algorithms - ESA 2014","author":"P Gawrychowski","year":"2014","unstructured":"Gawrychowski, P., Lewenstein, M., Nicholson, P.K.: Weighted ancestors in suffix trees. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 455\u2013466. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-44777-2_38"},{"key":"20_CR20","unstructured":"Gu, M., Farach, M., Beigel, R.: An efficient algorithm for dynamic text indexing. In: Proceedings of 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 697\u2013704 (1994)"},{"key":"20_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1007\/3-540-45061-0_73","volume-title":"Automata, Languages and Programming","author":"J K\u00e4rkk\u00e4inen","year":"2003","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P.: Simple linear work suffix array construction. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 943\u2013955. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-45061-0_73"},{"key":"20_CR22","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., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6, 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"20_CR23","unstructured":"Kopelowitz, T.: On-line indexing for general alphabets. In: Proceedings of 53rd IEEE Symposium on the Foundation of Computer Science (FOCS) (2012)"},{"key":"20_CR24","unstructured":"Kopelowitz, T., Lewenstein, M.: Dynamic weighted ancestors. In: Proceedings of 18th ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 565\u2013574 (2007)"},{"key":"20_CR25","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1002\/prot.340230308","volume":"23","author":"MR Lemer","year":"1995","unstructured":"Lemer, M.R., Rooman, M.J., Wodak, S.J.: Protein structure prediction by threading methods: evaluation of current techniques. Proteins 23, 337\u2013355 (1995)","journal-title":"Proteins"},{"key":"20_CR26","first-page":"707","volume":"10","author":"VI Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting, deletions, insertions and reversals. Soviet Phys. Dokl. 10, 707\u2013710 (1966)","journal-title":"Soviet Phys. Dokl."},{"key":"20_CR27","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. In: Proceedings of 1st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 319\u2013327 (1990)"},{"key":"20_CR28","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"EM McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM 23, 262\u2013272 (1976)","journal-title":"J. ACM"},{"key":"20_CR29","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Thorup, M.: Dynamic integer sets with optimal rank, select, and predecessor search. In: Proceedings of 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 166\u2013175 (2014)","DOI":"10.1109\/FOCS.2014.26"},{"key":"20_CR30","unstructured":"Rauhe, T., Alstrup, S., Brodal, G.S.: Pattern matching in dynamic texts. In: Proceedings of 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 819\u2013828 (2000)"},{"key":"20_CR31","doi-asserted-by":"crossref","unstructured":"Sahinalp, S.C., Vishkin, U.: Efficient approximate and dynamic matching of patterns using a labeling paradigm. In: Proceedings of 37th FOCS, pp. 320\u2013328 (1996)","DOI":"10.1109\/SFCS.1996.548491"},{"key":"20_CR32","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, 195\u2013197 (1981)","journal-title":"J. Mol. Biol."},{"key":"20_CR33","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14, 249\u2013260 (1995)","journal-title":"Algorithmica"},{"issue":"3","key":"20_CR34","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P Emde Boas van","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett. 6(3), 80\u201382 (1977)","journal-title":"Inf. Process. Lett."},{"key":"20_CR35","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proceeings of 14 IEEE Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-00479-8_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T05:41:35Z","timestamp":1751866895000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-00479-8_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030004781","9783030004798"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-00479-8_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"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":"Lima","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Peru","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 October 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 October 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/eventos.spc.org.pe\/spire2018\/","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"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"51","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"22","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"6","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"43% - 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"}},{"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"}},{"value":"3.8","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}}]}}