{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T07:33:58Z","timestamp":1783150438821,"version":"3.54.6"},"reference-count":34,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2018,8,3]],"date-time":"2018-08-03T00:00:00Z","timestamp":1533254400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["N2-0053"],"award-info":[{"award-number":["N2-0053"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["P2-0359"],"award-info":[{"award-number":["P2-0359"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We consider a sliding window W over a stream of characters from some alphabet of constant size. We want to look up a pattern in the current sliding window content and obtain all positions of the matches. We present an indexed version of the sliding window, based on a suffix tree. The data structure of size \u0398(|W|) has optimal time queries \u0398(m+occ) and amortized constant time updates, where m is the length of the query string and occ is its number of occurrences.<\/jats:p>","DOI":"10.3390\/a11080118","type":"journal-article","created":{"date-parts":[[2018,8,3]],"date-time":"2018-08-03T11:03:26Z","timestamp":1533294206000},"page":"118","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Sliding Suffix Tree"],"prefix":"10.3390","volume":"11","author":[{"given":"Andrej","family":"Brodnik","sequence":"first","affiliation":[{"name":"Faculty of Computer and Information Science, University of Ljubljana, 1000 Ljubljana, Slovenia"},{"name":"Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, 6000 Koper-Capodistria, Slovenia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matev\u017e","family":"Jekovec","sequence":"additional","affiliation":[{"name":"Faculty of Computer and Information Science, University of Ljubljana, 1000 Ljubljana, Slovenia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2018,8,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1216370.1216372","article-title":"Compressed full-text indexes","volume":"39","author":"Navarro","year":"2007","journal-title":"ACM Comput. Surv."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","article-title":"Replacing suffix trees with enhanced suffix arrays","volume":"2","author":"Abouelhoda","year":"2004","journal-title":"J. Discrete Algorithms"},{"key":"ref_3","unstructured":"Grossi, R., Gupta, A., and Vitter, J.S. (2003, January 12\u201314). High-Order Entropy-Compressed Text Indexes. Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","article-title":"Fast Pattern Matching in Strings","volume":"6","author":"Knuth","year":"1977","journal-title":"SIAM J. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/359842.359859","article-title":"A fast string searching algorithm","volume":"20","author":"Boyer","year":"1977","journal-title":"Commun. ACM"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","article-title":"Efficient randomized pattern-matching algorithms","volume":"31","author":"Karp","year":"1987","journal-title":"IBM J. Res. Dev."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Serna, M., Shaltiel, R., Jansen, K., and Rolim, J. (2010). Periodicity in Streams. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer.","DOI":"10.1007\/978-3-642-15369-3"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Giancarlo, R., and Manzini, G. (2011). Real-Time Streaming String-Matching. Combinatorial Pattern Matching, Springer.","DOI":"10.1007\/978-3-642-21458-5"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Casey, E. (2009). Handbook of Digital Forensics and Investigation, Elsevier Academic Press. [2nd ed.].","DOI":"10.1016\/B978-0-12-374267-4.00004-5"},{"key":"ref_10","unstructured":"Cox, R. (2018, August 02). Regular Expression Matching: the Virtual Machine Approach. Available online: https:\/\/swtch.com\/rsc\/regexp\/."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Peterson, G., and Shenoi, S. (2011). Searching Massive Data Streams Using Multipattern Regular Expressions. Advances in Digital Forensics VII, Springer.","DOI":"10.1007\/978-3-642-24212-0"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Agravat, D., Vaishnav, U., and Swadas, P.B. (2010, January 9\u201311). Modified Ant Miner for Intrusion Detection. Proceedings of the 2010 Second International Conference on Machine Learning and Computing, Bangalore, India.","DOI":"10.1109\/ICMLC.2010.52"},{"key":"ref_13","first-page":"51","article-title":"Analysis of neural networks usage for detection of a new attack in IDS","volume":"10","author":"Kukielka","year":"2010","journal-title":"Ann. UMCS Inform."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1145\/63334.63341","article-title":"Data compression with finite windows","volume":"32","author":"Fiala","year":"1989","journal-title":"Commun. ACM"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","article-title":"A Space-Economical Suffix Tree Construction Algorithm","volume":"23","author":"McCreight","year":"1976","journal-title":"J. ACM"},{"key":"ref_16","unstructured":"Larsson, N.J. (1999). Structures of String Matching and Data Compression. [Ph.D. Thesis, Lund University]."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01206331","article-title":"On-Line Construction of Suffix Trees","volume":"14","author":"Ukkonen","year":"1995","journal-title":"Algorithmica"},{"key":"ref_18","unstructured":"\u0160afr\u00e1nkov\u00e1, J. (2005). Suffix tree for a sliding window: An overview. Week of Doctoral Students, Matfyzpress."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1145\/28869.28873","article-title":"Complete Inverted Files for Efficient Text Retrieval and Analysis","volume":"34","author":"Blumer","year":"1987","journal-title":"J. ACM"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/j.dam.2004.04.012","article-title":"On-line construction of compact directed acyclic word graphs","volume":"146","author":"Inenaga","year":"2005","journal-title":"Discrete Appl. Math."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/S1570-8667(03)00064-9","article-title":"Compact directed acyclic word graphs for a sliding window","volume":"2","author":"Inenaga","year":"2004","journal-title":"J. Discrete Algorithms"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Ferreira, A., Oliveira, A., and Figueiredo, M. (2009, January 16\u201318). On the Use of Suffix Arrays for Memory-Efficient Lempel-Ziv Data Compression. Proceedings of the 2009 Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC.2009.50"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Ferreira, A., Oliveira, A., and Figueiredo, M. (2011, January 29\u201331). Sliding Window Update Using Suffix Arrays. Proceedings of the 2011 Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC.2011.60"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"4350","DOI":"10.1016\/j.tcs.2009.07.016","article-title":"A four-stage algorithm for updating a Burrows\u2013Wheeler transform","volume":"410","author":"Salson","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1145\/355541.355547","article-title":"On the sorting-complexity of suffix tree construction","volume":"47","author":"Ferragina","year":"2000","journal-title":"J. ACM"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Barsky, M., Stege, U., Thomo, A., and Upton, C. (2009). Suffix trees for very large genomic sequences. Proceeding of the 18th ACM conference on Information and knowledge management - CIKM \u201909, Hong Kong, China, 2\u20136 November 2009, ACM Press.","DOI":"10.1145\/1645953.1646134"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"49","DOI":"10.14778\/2047485.2047490","article-title":"ERA: Efficient serial and parallel suffix tree construction for very long strings","volume":"5","author":"Mansour","year":"2011","journal-title":"Proc. VLDB Endow."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Comin, M., and Farreras, M. (2013, January 15\u201318). Efficient parallel construction of suffix trees for genomes larger than main memory. Proceedings of the 20th European MPI Users\u2019 Group Meeting on EuroMPI \u201913, Madrid, Spain.","DOI":"10.1145\/2488551.2488579"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2661653","article-title":"A simple parallel cartesian tree algorithm and its application to parallel suffix tree construction","volume":"1","author":"Shun","year":"2014","journal-title":"ACM Trans. Parallel Comput."},{"key":"ref_30","unstructured":"Jekovec, M., and Brodnik, A. (2015). Parallel Query in the Suffix Tree, University of Ljubljana, Faculty of Computer and Information Science. Technical Report."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Inenaga, S., Sadakane, K., and Sakai, T. (2016, January 18\u201320). Parallel Lookups in String Indexes. Proceedings of the String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan.","DOI":"10.1007\/978-3-319-46049-9"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","article-title":"Compressed Suffix Trees with Full Functionality","volume":"41","author":"Sadakane","year":"2007","journal-title":"Theory Comput. Syst."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., and Fagerberg, R. (2006, January 22\u201326). Cache-oblivious string dictionaries. Proceedings of the 17th annual ACM-SIAM symposium on Discrete algorithm, SODA \u201906, Miami, Florida.","DOI":"10.1145\/1109557.1109621"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Brodnik, A., and Jekovec, M. (2018). Sliding Suffix Tree, University of Ljubljana, Faculty of Computer and Information Science. Technical Report.","DOI":"10.3390\/a11080118"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/8\/118\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:16:18Z","timestamp":1760195778000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/8\/118"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,3]]},"references-count":34,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2018,8]]}},"alternative-id":["a11080118"],"URL":"https:\/\/doi.org\/10.3390\/a11080118","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,3]]}}}