{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:45Z","timestamp":1740109305277,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,10,17]],"date-time":"2021-10-17T00:00:00Z","timestamp":1634428800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,10,17]],"date-time":"2021-10-17T00:00:00Z","timestamp":1634428800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100014434","name":"polish national agency for academic exchange","doi-asserted-by":"crossref","award":["PPN\/BEK\/2020\/1\/00444"],"award-info":[{"award-number":["PPN\/BEK\/2020\/1\/00444"]}],"id":[{"id":"10.13039\/501100014434","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001665","name":"agence nationale de la recherche","doi-asserted-by":"publisher","award":["ANR-20-CE48-0001"],"award-info":[{"award-number":["ANR-20-CE48-0001"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s00453-021-00876-x","type":"journal-article","created":{"date-parts":[[2021,10,17]],"date-time":"2021-10-17T08:55:31Z","timestamp":1634460931000},"page":"896-916","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Streaming Dictionary Matching with Mismatches"],"prefix":"10.1007","volume":"84","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7193-9432","authenticated-orcid":false,"given":"Tatiana","family":"Starikovskaya","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,17]]},"reference":[{"issue":"6","key":"876_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). https:\/\/doi.org\/10.1145\/360825.360855","journal-title":"Commun. ACM"},{"issue":"2","key":"876_CR2","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0196-6774(03)00097-X","volume":"50","author":"A Amir","year":"2004","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with $$k$$ mismatches. J. Algorithms 50(2), 257\u2013275 (2004). https:\/\/doi.org\/10.1016\/S0196-6774(03)00097-X","journal-title":"J. Algorithms"},{"key":"876_CR3","doi-asserted-by":"publisher","unstructured":"Belazzougui, D.: Succinct dictionary matching with no slowdown. In: Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching, pp. 88\u2013100 (2010). https:\/\/doi.org\/10.1007\/978-3-642-13509-5_9","DOI":"10.1007\/978-3-642-13509-5_9"},{"key":"876_CR4","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-642-19222-7_10","volume":"14","author":"D Belazzougui","year":"2012","unstructured":"Belazzougui, D.: Worst-case efficient single and multiple string matching on packed texts in the word-RAM model. J. Discrete Algorithms 14, 91\u2013106 (2012). https:\/\/doi.org\/10.1007\/978-3-642-19222-7_10","journal-title":"J. Discrete Algorithms"},{"key":"876_CR5","doi-asserted-by":"publisher","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Monotone minimal perfect hashing: searching a sorted table with O(1) accesses. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 785\u2013794 (2009). https:\/\/doi.org\/10.1137\/1.9781611973068.86","DOI":"10.1137\/1.9781611973068.86"},{"key":"876_CR6","doi-asserted-by":"publisher","unstructured":"Belazzougui, D., Boldi, P., Vigna, S.: Dynamic $$z$$-fast tries. In: Proceedings of the 17th International Symposium on String Processing and Information Retrieval, pp. 159\u2013172 (2010). https:\/\/doi.org\/10.1007\/978-3-642-16321-0_15","DOI":"10.1007\/978-3-642-16321-0_15"},{"key":"876_CR7","doi-asserted-by":"publisher","unstructured":"Belazzougui, D., Raffinot, M.: Average optimal string matching in packed strings. In: Proceedings of the 8th International Conference on Algorithms and Complexity, pp. 37\u201348 (2013). https:\/\/doi.org\/10.1007\/978-3-642-38233-8_4","DOI":"10.1007\/978-3-642-38233-8_4"},{"issue":"4","key":"876_CR8","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1145\/2635814","volume":"10","author":"D Breslauer","year":"2014","unstructured":"Breslauer, D., Galil, Z.: Real-time streaming string-matching. ACM Trans. Algorithms 10(4), 221\u20132212 (2014). https:\/\/doi.org\/10.1145\/2635814","journal-title":"ACM Trans. Algorithms"},{"key":"876_CR9","doi-asserted-by":"publisher","unstructured":"Clifford, R., Fontaine, A., Porat, E., Sach, B., Starikovskaya, T.: Dictionary matching in a stream. In: Proceedings of the 23rd Annual European Symposium on Algorithms, pp. 361\u2013372 (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_31","DOI":"10.1007\/978-3-662-48350-3_31"},{"key":"876_CR10","doi-asserted-by":"publisher","unstructured":"Clifford, R., Fontaine, A., Porat, E., Sach, B., Starikovskaya, T.: The k-mismatch problem revisited. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2039\u20132052 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch142","DOI":"10.1137\/1.9781611974331.ch142"},{"key":"876_CR11","doi-asserted-by":"publisher","unstructured":"Clifford, R., Kociumaka, T., Porat, E.: The streaming k-mismatch problem. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1106\u20131125 (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.68","DOI":"10.1137\/1.9781611975482.68"},{"key":"876_CR12","doi-asserted-by":"publisher","unstructured":"Cole, R., Gottlieb, L.A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 91\u2013100 (2004). https:\/\/doi.org\/10.1145\/1007352.1007374","DOI":"10.1145\/1007352.1007374"},{"key":"876_CR13","doi-asserted-by":"publisher","unstructured":"Commentz-Walter, B.: A string matching algorithm fast on the average. In: Proceedings of the 6th International Colloquium on Automata, Languages and Programming, pp. 118\u2013132 (1979). https:\/\/doi.org\/10.1007\/3-540-09510-1_10","DOI":"10.1007\/3-540-09510-1_10"},{"issue":"3","key":"876_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0020-0190(99)00092-7","volume":"71","author":"M Crochemore","year":"1999","unstructured":"Crochemore, M., Czumaj, A., Gasieniec, L., Lecroq, T., Plandowski, W., Rytter, W.: Fast practical multi-pattern matching. Inf. Process. Lett. 71(3), 107\u2013113 (1999)","journal-title":"Inf. Process. Lett."},{"key":"876_CR15","doi-asserted-by":"publisher","unstructured":"Dietzfelbinger, M., Meyer auf\u00a0der Heide, F.: Dynamic hashing in real time. In: Informatik: Festschrift zum 60. Geburtstag von G\u00fcnter Hotz, pp. 95\u2013119 (1992). https:\/\/doi.org\/10.1007\/978-3-322-95233-2_7","DOI":"10.1007\/978-3-322-95233-2_7"},{"issue":"1","key":"876_CR16","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/j.tcs.2007.06.006","volume":"385","author":"C Epifanio","year":"2007","unstructured":"Epifanio, C., Gabriele, A., Mignosi, F., Restivo, A., Sciortino, M.: Languages with mismatches. Theor. Comput. Sci. 385(1), 152\u2013166 (2007). https:\/\/doi.org\/10.1016\/j.tcs.2007.06.006","journal-title":"Theor. Comput. Sci."},{"key":"876_CR17","doi-asserted-by":"publisher","unstructured":"Fischer, J., Gagie, T., Gawrychowski, P., Kociumaka, T.: Approximating LZ77 via small-space multiple-pattern matching. In: Proceedings of the 23rd European Symposium on Algorithms, pp. 533\u2013544 (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_45","DOI":"10.1007\/978-3-662-48350-3_45"},{"key":"876_CR18","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Landau, G.M., Starikovskaya, T.: Fast entropy-bounded string dictionary look-up with mismatches. In: Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, vol. 117, pp. 66:1\u201366:15 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2018.66","DOI":"10.4230\/LIPIcs.MFCS.2018.66"},{"key":"876_CR19","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Starikovskaya, T.: Streaming dictionary matching with mismatches. In: Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching, pp. 21:1\u201321:15 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2019.21","DOI":"10.4230\/LIPIcs.CPM.2019.21"},{"key":"876_CR20","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Uzna\u0144ski, P.: Towards unified approximate pattern matching for Hamming and $$L_1$$ distance. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, vol. 107, pp. 62:1\u201362:13 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.62","DOI":"10.4230\/LIPIcs.ICALP.2018.62"},{"key":"876_CR21","doi-asserted-by":"publisher","unstructured":"Golan, S., Kociumaka, T., Kopelowitz, T., Porat, E.: Dynamic dictionary matching in the online model. In: Proceedings of the 16th International Symposium on Algorithms and Data Structures, Lecture Notes in Computer Science, vol. 11646, pp. 409\u2013422 (2019). https:\/\/doi.org\/10.1007\/978-3-030-24766-9_30","DOI":"10.1007\/978-3-030-24766-9_30"},{"key":"876_CR22","doi-asserted-by":"publisher","unstructured":"Golan, S., Kociumaka, T., Kopelowitz, T., Porat, E.: The streaming k-mismatch problem: tradeoffs between space and total time. In: Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, vol. 161, pp. 15:1\u201315:15 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2020.15","DOI":"10.4230\/LIPIcs.CPM.2020.15"},{"key":"876_CR23","doi-asserted-by":"publisher","unstructured":"Golan, S., Kopelowitz, T., Porat, E.: Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, pp. 65:1\u201365:16 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.65","DOI":"10.4230\/LIPIcs.ICALP.2018.65"},{"key":"876_CR24","doi-asserted-by":"publisher","unstructured":"Golan, S., Porat, E.: Real-time streaming multi-pattern search for constant alphabet. In: Proceedings of the 25th Annual European Symposium on Algorithms, vol.\u00a087, pp. 41:1\u201341:15 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.41","DOI":"10.4230\/LIPIcs.ESA.2017.41"},{"key":"876_CR25","doi-asserted-by":"publisher","unstructured":"Hon, W.K., Ku, T.H., Shah, R., Thankachan, S.V., Vitter, J.S.: Faster compressed dictionary matching. In: Proceedings of the 17th International Symposium on String Processing and Information Retrieval, pp. 191\u2013200 (2010). https:\/\/doi.org\/10.1007\/978-3-642-16321-0_19","DOI":"10.1007\/978-3-642-16321-0_19"},{"issue":"1","key":"876_CR26","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/j.tcs.2005.11.022","volume":"352","author":"TND Huynh","year":"2006","unstructured":"Huynh, T.N.D., Hon, W.K., Lam, T.W., Sung, W.K.: Approximate string matching using compressed suffix arrays. J. Theor. Comput. Sci. 352(1), 240\u2013249 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2005.11.022","journal-title":"J. Theor. Comput. Sci."},{"issue":"2","key":"876_CR27","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"RM Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249\u2013260 (1987). https:\/\/doi.org\/10.1147\/rd.312.0249","journal-title":"IBM J. Res. Dev."},{"key":"876_CR28","doi-asserted-by":"publisher","unstructured":"Kopelowitz, T., Porat, E., Rozen, Y.: Succinct online dictionary matching with improved worst-case guarantees. In: Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, vol.\u00a054, pp. 6:1\u20136:13 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2016.6","DOI":"10.4230\/LIPIcs.CPM.2016.6"},{"key":"876_CR29","doi-asserted-by":"publisher","unstructured":"Kosolobov, D., Sivukhin, N.: Compressed multiple pattern matching. In: Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching, pp. 13:1\u201313:14 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2019.13","DOI":"10.4230\/LIPIcs.CPM.2019.13"},{"key":"876_CR30","doi-asserted-by":"publisher","unstructured":"Kremer, I., Nisan, N., Ron, D.: On randomized one-round communication complexity. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pp. 596\u2013605 (1995). https:\/\/doi.org\/10.1007\/s000370050018","DOI":"10.1007\/s000370050018"},{"issue":"3","key":"876_CR31","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/s00453-007-9104-8","volume":"51","author":"TW Lam","year":"2008","unstructured":"Lam, T.W., Sung, W.K., Wong, S.S.: Improved approximate string matching using compressed suffix data structures. J. Algorithmica 51(3), 298\u2013314 (2008). https:\/\/doi.org\/10.1007\/s00453-007-9104-8","journal-title":"J. Algorithmica"},{"key":"876_CR32","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. Theor. Comput. Sci. 43, 239\u2013249 (1986). https:\/\/doi.org\/10.1016\/0304-3975(86)90178-7","journal-title":"Theor. Comput. Sci."},{"key":"876_CR33","doi-asserted-by":"publisher","unstructured":"Porat, B., Porat, E.: Exact and approximate pattern matching in the streaming model. In: Proceedings of the 50th Annual Symposium on Foundations of Computer Science, pp. 315\u2013323 (2009). https:\/\/doi.org\/10.1109\/FOCS.2009.11","DOI":"10.1109\/FOCS.2009.11"},{"issue":"4","key":"876_CR34","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/j.jda.2010.08.002","volume":"8","author":"D Tsur","year":"2010","unstructured":"Tsur, D.: Fast index for approximate string matching. J. Discrete Algorithms 8(4), 339\u2013345 (2010). https:\/\/doi.org\/10.1016\/j.jda.2010.08.002","journal-title":"J. Discrete Algorithms"},{"key":"876_CR35","unstructured":"Wu, S., Manber, U.: Agrep\u2014a fast approximate pattern-matching tool. In: Proceedings of the USENIX Technical Conference, pp. 153\u2013162 (1992)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00876-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00876-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00876-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T15:08:17Z","timestamp":1647443297000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00876-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,17]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["876"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00876-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,10,17]]},"assertion":[{"value":"27 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}