{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T06:51:15Z","timestamp":1784875875128,"version":"3.55.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2020,6,20]],"date-time":"2020-06-20T00:00:00Z","timestamp":1592611200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,20]],"date-time":"2020-06-20T00:00:00Z","timestamp":1592611200000},"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":["Algorithmica"],"published-print":{"date-parts":[[2020,11]]},"DOI":"10.1007\/s00453-020-00732-4","type":"journal-article","created":{"date-parts":[[2020,6,20]],"date-time":"2020-06-20T05:02:24Z","timestamp":1592629344000},"page":"3390-3412","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Efficient Online String Matching Based on Characters Distance Text Sampling"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5937-5796","authenticated-orcid":false,"given":"Simone","family":"Faro","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francesco Pio","family":"Marino","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arianna","family":"Pavone","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,6,20]]},"reference":[{"key":"732_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, London (1974)"},{"key":"732_CR2","series-title":"NATO Advanced Science Institutes, Series F","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-642-82456-2_6","volume-title":"Combinatorial Algorithms on Words","author":"A Apostolico","year":"1985","unstructured":"Apostolico, A.: The myriad virtues of suffix trees. In: Apostolico, A., Galil, Z. (eds.) Combinatorial Algorithms on Words. NATO Advanced Science Institutes, Series F, vol. 12, pp. 85\u201396. Springer, Berlin (1985)"},{"issue":"10","key":"732_CR3","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"RS Boyer","year":"1977","unstructured":"Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Commun. ACM 20(10), 762\u2013772 (1977)","journal-title":"Commun. ACM"},{"issue":"2","key":"732_CR4","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1142\/S0129054112400163","volume":"23","author":"D Cantone","year":"2012","unstructured":"Cantone, D., Faro, S., Giaquinta, E.: Adapting Boyer-Moore-like algorithms for searching Huffman encoded texts. Int. J. Found. Comput. Sci. 23(2), 343\u2013356 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"732_CR5","first-page":"42","volume":"2017","author":"D Cantone","year":"2017","unstructured":"Cantone, D., Faro, S., Pavone, A.: Speeding up string matching by weak factor recognition. Stringology 2017, 42\u201350 (2017)","journal-title":"Stringology"},{"key":"732_CR6","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.jda.2010.09.004","volume":"11","author":"F Claude","year":"2012","unstructured":"Claude, F., Navarro, G., Peltola, H., Salmela, L., Tarhio, J.: String matching with alphabet sampling. J. Discrete Algorithms 11, 37\u201350 (2012)","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"732_CR7","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF01185427","volume":"12","author":"M Crochemore","year":"1994","unstructured":"Crochemore, M., Czumaj, A., Gasieniec, L., Jarominek, S., Lecroq, T., Plandowski, W., Rytter, W.: Speeding up two string-matching algorithms. Algorithmica 12(4), 247\u2013267 (1994)","journal-title":"Algorithmica"},{"issue":"2","key":"732_CR8","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/2431211.2431212","volume":"45","author":"S Faro","year":"2013","unstructured":"Faro, S., Lecroq, T.: The exact online string matching problem: a review of the most recent results. ACM Comput. Surv. 45(2), 13 (2013)","journal-title":"ACM Comput. Surv."},{"key":"732_CR9","unstructured":"Faro, S., Lecroq, T., Borz\u00ec, S., Di Mauro, S., Maggio, A.: The String Matching Algorithms Research Tool. In Procedings of Stringology, pp. 99\u2013111, (2016)"},{"issue":"4","key":"732_CR10","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"issue":"6","key":"732_CR11","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1016\/j.ipl.2006.04.020","volume":"100","author":"K Fredriksson","year":"2006","unstructured":"Fredriksson, K., Grabowski, S.: A general compression algorithm that supports fast searching. Inf. Process. Lett. 100(6), 226\u2013232 (2006)","journal-title":"Inf. Process. Lett."},{"key":"732_CR12","doi-asserted-by":"crossref","unstructured":"Grabowski, S., Raniszewski, M.: Sampling the suffix array with minimizers. In: Porceedings of String Processing and Information Retrieval (SPIRE 2015), Lecture Notes in Computer Science, vol 9309, Springer, pp. 287\u2013298 (2015)","DOI":"10.1007\/978-3-319-23826-5_28"},{"issue":"6","key":"732_CR13","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1002\/spe.4380100608","volume":"10","author":"RN Horspool","year":"1980","unstructured":"Horspool, R.N.: Practical fast searching in strings. Softw. Pract. Exp. 10(6), 501\u2013506 (1980)","journal-title":"Softw. Pract. Exp."},{"key":"732_CR14","doi-asserted-by":"crossref","unstructured":"Karkkainen, J., Ukkonen, E.: Sparse suffix trees. In: Proceedings of 2nd Annual International Conference on Computing and Combinatorics (COCOON), LNCS 1090, pp. 219\u2013230 (1996)","DOI":"10.1007\/3-540-61332-3_155"},{"key":"732_CR15","unstructured":"Klein, S.T., Shapira, D.: A new compression method for compressed matching. In: Data Compression Conference, IEEE. pp. 400\u2013409 (2000)"},{"issue":"2","key":"732_CR16","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(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"732_CR17","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/248625.248639","volume":"15","author":"Manber","year":"1997","unstructured":"Manber: A text compression scheme that allows fast searching directly in the compressed file. ACM Trans. Inf. Syst. 15(2), 124\u2013136 (1997)","journal-title":"ACM Trans. Inf. Syst."},{"issue":"5","key":"732_CR18","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 online string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"732_CR19","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1145\/348751.348754","volume":"18","author":"E Moura","year":"2000","unstructured":"Moura, E., Navarro, G., Ziviani, N., Baeza-Yates, R.: Fast and flexible word searching on compressed text. ACM Trans. Inf. Syst. 18(2), 113\u2013139 (2000)","journal-title":"ACM Trans. Inf. Syst."},{"key":"732_CR20","doi-asserted-by":"publisher","first-page":"1107","DOI":"10.1002\/spe.663","volume":"35","author":"G Navarro","year":"2005","unstructured":"Navarro, G., Tarhio, J.: LZgrep: a Boyer-Moore string matching tool for Ziv-Lempel compressed text. Softw. Pract. Exp. 35, 1107\u20131130 (2005)","journal-title":"Softw. Pract. Exp."},{"key":"732_CR21","doi-asserted-by":"crossref","unstructured":"Shibata, Y., Kida, T., Fukamachi, S., Takeda, M., Shinohara, A., Shinohara, T., Arikawa, S.: Speeding Up Pattern Matching by Text Compression. In: CIAC 306\u2013315 (2000)","DOI":"10.1007\/3-540-46521-9_25"},{"issue":"3","key":"732_CR22","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1137\/0208029","volume":"8","author":"AC Yao","year":"1979","unstructured":"Yao, A.C.: The complexity of pattern matching for a random string. SIAM J. Comput. 8(3), 368\u2013387 (1979)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00732-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00732-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00732-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,19]],"date-time":"2021-06-19T23:25:11Z","timestamp":1624145111000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00732-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,20]]},"references-count":22,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["732"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00732-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,20]]},"assertion":[{"value":"23 April 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}