{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T19:15:29Z","timestamp":1770232529468,"version":"3.49.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,7,1]],"date-time":"2013-07-01T00:00:00Z","timestamp":1372636800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Project of DEGP"},{"DOI":"10.13039\/501100004602","name":"Program for New Century Excellent Talents in University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004602","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities of China","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:p>\n            This article presents an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            )-time algorithm called SACA-K for sorting the suffixes of an input string\n            <jats:italic>T<\/jats:italic>\n            [0,\n            <jats:italic>n<\/jats:italic>\n            -1] over an alphabet\n            <jats:italic>A<\/jats:italic>\n            [0,\n            <jats:italic>K<\/jats:italic>\n            -1]. The problem of sorting the suffixes of\n            <jats:italic>T<\/jats:italic>\n            is also known as constructing the suffix array (SA) for\n            <jats:italic>T<\/jats:italic>\n            . The theoretical memory usage of SACA-K is\n            <jats:italic>n<\/jats:italic>\n            <jats:italic>log<\/jats:italic>\n            <jats:italic>K<\/jats:italic>\n            +\n            <jats:italic>n<\/jats:italic>\n            <jats:italic>log<\/jats:italic>\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>K<\/jats:italic>\n            <jats:italic>log<\/jats:italic>\n            <jats:italic>n<\/jats:italic>\n            bits. Moreover, we also have a practical implementation for SACA-K that uses\n            <jats:italic>n<\/jats:italic>\n            bytes + (\n            <jats:italic>n<\/jats:italic>\n            + 256) words and is suitable for strings over any alphabet up to full ASCII, where a word is log\n            <jats:italic>n<\/jats:italic>\n            bits. In our experiment, SACA-K outperforms SA-IS that was previously the most time- and space-efficient linear-time SA construction algorithm (SACA). SACA-K is around 33% faster and uses a smaller deterministic workspace of\n            <jats:italic>K<\/jats:italic>\n            words, where the workspace is the space needed beyond the input string and the output SA. Given\n            <jats:italic>K<\/jats:italic>\n            =\n            <jats:italic>O<\/jats:italic>\n            (1), SACA-K runs in linear time and\n            <jats:italic>O<\/jats:italic>\n            (1) workspace. To the best of our knowledge, such a result is the first reported in the literature with a practical source code publicly available.\n          <\/jats:p>","DOI":"10.1145\/2493175.2493180","type":"journal-article","created":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T15:14:00Z","timestamp":1375370040000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":67,"title":["Practical linear-time\n            <i>O<\/i>\n            (1)-workspace suffix sorting for constant alphabets"],"prefix":"10.1145","volume":"31","author":[{"given":"Ge","family":"Nong","sequence":"first","affiliation":[{"name":"Sun Yat-sen University, China"}]}],"member":"320","published-online":{"date-parts":[[2013,8,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Burkhardt S.\n     and \n      K\u00e4rkk\u00e4inen J\n  . \n  2003\n  . Fast lightweight suffix array construction and checking. In Combinatorial Pattern Matching Lecture Notes in Computer Science vol. \n  2676 Spriger Verlag Berlin Heidelberg 55--69.   Burkhardt S. and K\u00e4rkk\u00e4inen J. 2003. Fast lightweight suffix array construction and checking. In Combinatorial Pattern Matching Lecture Notes in Computer Science vol. 2676 Spriger Verlag Berlin Heidelberg 55--69.","DOI":"10.1007\/3-540-44888-8_5"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1227161.1402296"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9535-0"},{"key":"e_1_2_1_4_1","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms and Data Structures","author":"Fischer J.","unstructured":"Fischer , J. 2011. Inducing the LCP-array . In Algorithms and Data Structures , Lecture Notes in Computer Science , vol. 6844 , Spriger Verlag , Berlin Heidelberg , 374--385. Fischer, J. 2011. Inducing the LCP-array. In Algorithms and Data Structures, Lecture Notes in Computer Science, vol. 6844, Spriger Verlag, Berlin Heidelberg, 374--385."},{"key":"e_1_2_1_5_1","volume-title":"Languages and Programming. Lecture Notes in Computer Science","volume":"4596","author":"Franceschini G.","unstructured":"Franceschini , G. and Muthukrishnan , S . 2007. In-place suffix sorting. In Automata , Languages and Programming. Lecture Notes in Computer Science , vol. 4596 , Spriger Verlag, Berlin Heidelberg, 533--545. Franceschini, G. and Muthukrishnan, S. 2007. In-place suffix sorting. In Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 4596, Spriger Verlag, Berlin Heidelberg, 533--545."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS'03)","author":"Hon W. K.","unstructured":"Hon , W. K. , Sadakane , K. , and Sung , W. K . 2003. Breaking a time-and-space barrier for constructing full-text indices . In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS'03) . 251--260. Hon, W. K., Sadakane, K., and Sung, W. K. 2003. Breaking a time-and-space barrier for constructing full-text indices. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS'03). 251--260."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the String Processing and Information Retrieval Symposium and International Workshop on Group-ware (SPIRE'99)","author":"Itoh H.","unstructured":"Itoh , H. and Tanaka , H . 1999. An efficient method for in memory construction of suffix arrays . In Proceedings of the String Processing and Information Retrieval Symposium and International Workshop on Group-ware (SPIRE'99) . 81--88. Itoh, H. and Tanaka, H. 1999. An efficient method for in memory construction of suffix arrays. In Proceedings of the String Processing and Information Retrieval Symposium and International Workshop on Group-ware (SPIRE'99). 81--88."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217858"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.019"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.002"},{"key":"e_1_2_1_11_1","unstructured":"Larsson N. J. and Sadakane K. 1999. faster suffix sorting. Tech. rep. LU-CS-TR:99-214 LUNDFD6\/(NFCS-3140)\/1--20\/(1999). Department of Computer Science Lund University Sweden.  Larsson N. J. and Sadakane K. 1999. faster suffix sorting. Tech. rep. LU-CS-TR:99-214 LUNDFD6\/(NFCS-3140)\/1--20\/(1999). Department of Computer Science Lund University Sweden."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 17th Australasian Workshop on Combinatorial Algorithms. 16--29","author":"Maniscalco M. A.","unstructured":"Maniscalco , M. A. and Puglisi , S. J . 2006. Faster lightweight suffix array construction . In Proceedings of the 17th Australasian Workshop on Combinatorial Algorithms. 16--29 . Maniscalco, M. A. and Puglisi, S. J. 2006. Faster lightweight suffix array construction. In Proceedings of the 17th Australasian Workshop on Combinatorial Algorithms. 16--29."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1094-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2010.188"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03784-9_9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242471.1242472"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/874052.874842"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 7th Workshop on Algorithm Engineering and Experiments and the 2nd Workshop on Analytic Algorithms and Combinations (ALENEX\/ANALCO'05)","author":"Sch\u00fcrmann K. B.","unstructured":"Sch\u00fcrmann , K. B. and Stoye , J . 2005. An incomplex algorithm for fast suffix array construction . In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments and the 2nd Workshop on Analytic Algorithms and Combinations (ALENEX\/ANALCO'05) . 77--85. Sch\u00fcrmann, K. B. and Stoye, J. 2005. An incomplex algorithm for fast suffix array construction. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments and the 2nd Workshop on Analytic Algorithms and Combinations (ALENEX\/ANALCO'05). 77--85."}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2493175.2493180","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2493175.2493180","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:33Z","timestamp":1750235973000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2493175.2493180"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["10.1145\/2493175.2493180"],"URL":"https:\/\/doi.org\/10.1145\/2493175.2493180","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"value":"1046-8188","type":"print"},{"value":"1558-2868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7]]},"assertion":[{"value":"2012-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-08-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}