{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,14]],"date-time":"2025-02-14T05:16:20Z","timestamp":1739510180837,"version":"3.37.0"},"reference-count":22,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>We introduce the VST (virtual suffix tree), an efficient data structure for suffix trees and suffix arrays. Starting from the suffix array, we construct the suffix tree, from which we derive the virtual suffix tree. Later, we remove the intermediate step of suffix tree construction, and build the VST directly from the suffix array. The VST provides the same functionality as the suffix tree, including suffix links, but at a much smaller space requirement. It has the same linear time construction even for large alphabets, \u03a3, requires O(n) space to store (n is the string length), and allows searching for a pattern of length m to be performed in O(m log |\u03a3|) time, the same time needed for a suffix tree. Given the VST, we show an algorithm that computes all the suffix links in linear time, independent of \u03a3. The VST requires less space than other recently proposed data structures for suffix trees and suffix arrays, such as the enhanced suffix array [1], and the linearized suffix tree [17]. On average, the space requirement (including that for suffix arrays and suffix links) is 13.8n bytes for the regular VST, and 12.05n bytes in its compact form.<\/jats:p>","DOI":"10.1142\/s0129054109007066","type":"journal-article","created":{"date-parts":[[2009,11,23]],"date-time":"2009-11-23T01:28:50Z","timestamp":1258939730000},"page":"1109-1133","source":"Crossref","is-referenced-by-count":2,"title":["THE VIRTUAL SUFFIX TREE"],"prefix":"10.1142","volume":"20","author":[{"given":"JIE","family":"LIN","sequence":"first","affiliation":[{"name":"Lane Department of Computer Science and Electrical Engineering, West Virginia University, Morgantown, WV 26506, USA"}]},{"given":"YUE","family":"JIANG","sequence":"additional","affiliation":[{"name":"Lane Department of Computer Science and Electrical Engineering, West Virginia University, Morgantown, WV 26506, USA"}]},{"given":"DON","family":"ADJEROH","sequence":"additional","affiliation":[{"name":"Lane Department of Computer Science and Electrical Engineering, West Virginia University, Morgantown, WV 26506, USA"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00065-0"},{"key":"rf2","doi-asserted-by":"crossref","unstructured":"D.\u00a0Adjeroh and F.\u00a0Nan, DCC (IEEE Computer Society, 2008)\u00a0p. 502.","DOI":"10.1109\/DCC.2008.99"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-78909-5"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380250203"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/10719839_9"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185431"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335352"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355547"},{"volume":"33","journal-title":"Software \u2014 Practice and Experience","author":"Giegerich R.","key":"rf10"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402354"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217858"},{"journal-title":"Algorithmica","author":"Kim D.-K.","key":"rf17"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.019"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.002"},{"volume":"101","journal-title":"Information Processing Letters","author":"Maa\u03b2 M. G.","key":"rf20"},{"key":"rf21","first-page":"191","volume":"56","author":"M\u00e4kinen V.","journal-title":"Fundam. Inform."},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1151"},{"volume":"39","journal-title":"ACM Computing Surveys","author":"Puglisi S. J.","key":"rf27"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206331"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054109007066","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T10:55:32Z","timestamp":1739444132000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054109007066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":22,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1142\/S0129054109007066"],"URL":"https:\/\/doi.org\/10.1142\/s0129054109007066","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}