{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T00:00:14Z","timestamp":1758585614363,"version":"3.44.0"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032052278","type":"print"},{"value":"9783032052285","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,9,22]],"date-time":"2025-09-22T00:00:00Z","timestamp":1758499200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,22]],"date-time":"2025-09-22T00:00:00Z","timestamp":1758499200000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-05228-5_17","type":"book-chapter","created":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T17:01:23Z","timestamp":1758474083000},"page":"202-216","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["String Matching with\u00a0a\u00a0Dynamic Pattern"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-9435-5323","authenticated-orcid":false,"given":"Bruno","family":"Monteiro","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4608-4559","authenticated-orcid":false,"given":"Vinicius","family":"dos Santos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,22]]},"reference":[{"issue":"6","key":"17_CR1","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18(6), 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"key":"17_CR2","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: Pattern matching in dynamic texts. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 819\u2013828 (2000)"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Amir, A., Kondratovsky, E.: Searching for a modified pattern in a changing text. In: International Symposium on String Processing and Information Retrieval, pp. 241\u2013253. Springer (2018)","DOI":"10.1007\/978-3-030-00479-8_20"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"Amir, A., Kopelowitz, T., Lewenstein, M., Lewenstein, N.: Towards real-time suffix tree construction. In: International Symposium on String Processing and Information Retrieval, pp. 67\u201378. Springer (2005)","DOI":"10.1007\/11575832_9"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Amir, A., Landau, G.M., Lewenstein, M., Sokol, D.: Dynamic text and static pattern matching. ACM Trans. Algorithms (TALG) 3(2), 19\u2013es (2007)","DOI":"10.1145\/1240233.1240242"},{"key":"17_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"MA Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA Problem Revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88\u201394. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/10719839_9"},{"key":"17_CR7","unstructured":"Boneh, I., Golan, S., Kraus, M.: $$\\backslash ^{~}$$ optimal algorithm for fully dynamic lz77. arXiv preprint arXiv:2502.12000 (2025)"},{"key":"17_CR8","unstructured":"Charalampopoulos, P., Gawrychowski, P., Pokorski, K.: Dynamic longest common substring in polylogarithmic time. arXiv preprint arXiv:2006.02408 (2020)"},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"Cole, R., Kopelowitz, T., Lewenstein, M.: Suffix trays and suffix Trists: structures for faster text indexing. In: International Colloquium on Automata, Languages, and Programming, pp. 358\u2013369. Springer (2006)","DOI":"10.1007\/11786986_32"},{"key":"17_CR10","unstructured":"Cole, R., Lewenstein, M.: Multidimensional matching and fast search in suffix trees. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 851\u2013852 (2003)"},{"key":"17_CR11","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms. MIT Press (2022)"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Das, R., He, M., Kondratovsky, E., Munro, J.I., Wu, K.: Internal masked prefix sums and its connection to fully internal measurement queries. In: International Symposium on String Processing and Information Retrieval, pp. 217\u2013232. Springer (2022)","DOI":"10.1007\/978-3-031-20643-6_16"},{"issue":"1","key":"17_CR13","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"JR Driscoll","year":"1989","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. J. Comput. Syst. Sci. 38(1), 86\u2013124 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: Proceedings 38th Annual Symposium on Foundations of Computer Science, pp. 137\u2013143. IEEE (1997)","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"3","key":"17_CR15","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":"17_CR16","unstructured":"Fischer, M.J., Paterson, M.S.: String matching and other products. In: Complexity of Computation, RM Karp (editor), SIAM-AMS Proceedings. vol.\u00a07, pp. 113\u2013125 (1974)"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Karczmarz, A., Kociumaka, T., \u0141cki, J., Sankowski, P.: Optimal dynamic strings. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1509\u20131528. SIAM (2018)","DOI":"10.1137\/1.9781611975031.99"},{"key":"17_CR18","unstructured":"Gu, M., Farach, M., Beigel, R.: An efficient algorithm for dynamic text indexing. In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 697\u2013704. SODA \u201994, Society for Industrial and Applied Mathematics, USA (1994)"},{"issue":"1\u20133","key":"17_CR19","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/j.tcs.2005.11.022","volume":"352","author":"TN Huynh","year":"2006","unstructured":"Huynh, T.N., Hon, W.K., Lam, T.W., Sung, W.K.: Approximate string matching using compressed suffix arrays. Theoret. Comput. Sci. 352(1\u20133), 240\u2013249 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"17_CR20","first-page":"520","volume":"48","author":"A Ivanov","year":"1984","unstructured":"Ivanov, A.: Distinguishing an approximate word s inclusion on turing machine in real time. Izv. Acad. Nauk USSR Ser. Mat 48, 520\u2013568 (1984)","journal-title":"Izv. Acad. Nauk USSR Ser. Mat"},{"key":"17_CR21","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P.: Simple linear work suffix array construction. In: International Colloquium on Automata, Languages, and Programming, pp. 943\u2013955. Springer (2003)","DOI":"10.1007\/3-540-45061-0_73"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: CPM. vol.\u00a02089, pp. 181\u2013192. Springer (2001)","DOI":"10.1007\/3-540-48194-X_17"},{"key":"17_CR23","doi-asserted-by":"crossref","unstructured":"Kempa, D., Kociumaka, T.: Dynamic suffix array with polylogarithmic queries and updates. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1657\u20131670 (2022)","DOI":"10.1145\/3519935.3520061"},{"issue":"2\u20134","key":"17_CR24","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.jda.2004.08.019","volume":"3","author":"DK Kim","year":"2005","unstructured":"Kim, D.K., Sim, J.S., Park, H., Park, K.: Constructing suffix arrays in linear time. J. Discrete Algorithms 3(2\u20134), 126\u2013142 (2005)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"17_CR25","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)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"17_CR26","doi-asserted-by":"publisher","first-page":"1524","DOI":"10.1137\/23M1567618","volume":"53","author":"T Kociumaka","year":"2024","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W., Wale\u0144, T.: Internal pattern matching queries in a text and applications. SIAM J. Comput. 53(5), 1524\u20131577 (2024)","journal-title":"SIAM J. Comput."},{"key":"17_CR27","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(86)90178-7","volume":"43","author":"GM Landau","year":"1986","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching with $$k$$ mismatches. Theoret. Comput. Sci. 43, 239\u2013249 (1986)","journal-title":"Theoret. Comput. Sci."},{"issue":"5","key":"17_CR28","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"key":"17_CR29","unstructured":"Monteiro, B.: String Matching with a Dynamic Pattern. Master\u2019s thesis, Universidade Federal de Minas Gerais (2024)"},{"key":"17_CR30","volume-title":"A linear pattern-matching algorithm","author":"J Morris Jr","year":"1970","unstructured":"Morris, J., Jr., Pratt, V.: A linear pattern-matching algorithm. University of California, Berkeley (1970)"},{"issue":"7","key":"17_CR31","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N Sarnak","year":"1986","unstructured":"Sarnak, N., Tarjan, R.E.: Planar point location using persistent search trees. Commun. ACM 29(7), 669\u2013679 (1986)","journal-title":"Commun. ACM"},{"key":"17_CR32","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory (swat 1973), pp. 1\u201311. IEEE (1973)","DOI":"10.1109\/SWAT.1973.13"}],"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-032-05228-5_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T17:02:54Z","timestamp":1758474174000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-05228-5_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,22]]},"ISBN":["9783032052278","9783032052285"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-05228-5_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,22]]},"assertion":[{"value":"22 September 2025","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":"London","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","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":"8 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.google.com\/view\/spire-2025\/home","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}