{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:15:46Z","timestamp":1760238946900,"version":"build-2065373602"},"reference-count":20,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,9,18]],"date-time":"2020-09-18T00:00:00Z","timestamp":1600387200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP16H02783","JP20H04141"],"award-info":[{"award-number":["JP16H02783","JP20H04141"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-07185-2020"],"award-info":[{"award-number":["RGPIN-07185-2020"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["319454"],"award-info":[{"award-number":["319454"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We extend recent results regarding finding shortest unique substrings (SUSs) to obtain new time-space tradeoffs for this problem and the generalization of finding k-mismatch SUSs. Our new results include the first algorithm for finding a k-mismatch SUS in sublinear space, which we obtain by extending an algorithm by Senanayaka (2019) and combining it with a result on sketching by Gawrychowski and Starikovskaya (2019). We first describe how, given a text T of length n and m words of workspace, with high probability we can find an SUS of length L in O(n(L\/m)logL) time using random access to T, or in O(n(L\/m)log2(L)loglog\u03c3) time using O((L\/m)log2L) sequential passes over T. We then describe how, for constant k, with high probability, we can find a k-mismatch SUS in O(n1+\u03f5L\/m) time using O(n\u03f5L\/m) sequential passes over T, again using only m words of workspace. Finally, we also describe a deterministic algorithm that takes O(n\u03c4log\u03c3logn) time to find an SUS using O(n\/\u03c4) words of workspace, where \u03c4 is a parameter.<\/jats:p>","DOI":"10.3390\/a13090234","type":"journal-article","created":{"date-parts":[[2020,9,18]],"date-time":"2020-09-18T07:27:33Z","timestamp":1600414053000},"page":"234","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["More Time-Space Tradeoffs for Finding a Shortest Unique Substring"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6856-5185","authenticated-orcid":false,"given":"Hideo","family":"Bannai","sequence":"first","affiliation":[{"name":"M&amp;D Data Science Center, Tokyo Medical and Dental University, Tokyo 113-8510, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3689-327X","authenticated-orcid":false,"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, Dalhousie University, Halifax, NS B3H 4R2, Canada"}]},{"given":"Gary","family":"Hoppenworth","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Mathematics, University of Central Florida, Orlando, FL 32816, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7668-7636","authenticated-orcid":false,"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, 00100 Helsinki, Finland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1966-1808","authenticated-orcid":false,"given":"Lu\u00eds M. S.","family":"Russo","sequence":"additional","affiliation":[{"name":"INESC-ID and Instituto Superior T\u00e9cnico, Universidade de Lisboa, 1649-013 Lisboa, Portugal"}]}],"member":"1968","published-online":{"date-parts":[[2020,9,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Abedin, P., K\u00fclekci, M.O., and Thankachan, S.V. (2020). A Survey on Shortest Unique Substring Queries. Algorithms, 13.","DOI":"10.3390\/a13090224"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Haubold, B., Pierstorff, N., M\u00f6ller, F., and Wiehe, T. (2005). Genome comparison without alignment using shortest unique substrings. BMC Bioinform., 6.","DOI":"10.1186\/1471-2105-6-123"},{"key":"ref_3","unstructured":"Pei, J., Wu, W.C.H., and Yeh, M.Y. (2013, January 8\u201312). On shortest unique substring queries. Proceedings of the IEEE 29th International Conference on Data Engineering (ICDE), Brisbane, QLD, Australia."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Ada\u015f, B., Bayraktar, E., Faro, S., Moustafa, I.E., and K\u00fclekci, M.O. (2015, January 18\u201320). Nucleotide sequence alignment and compression via shortest unique substring. Proceedings of the International Conference on Bioinformatics and Biomedical Engineering, Shanghai, China.","DOI":"10.1007\/978-3-319-16480-9_36"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Hu, X., Pei, J., and Tao, Y. (2014, January 20\u201322). Shortest unique queries on strings. Proceedings of the International Symposium on String Processing and Information Retrieval, Ouro Preto, Brazil.","DOI":"10.1007\/978-3-319-11918-2_16"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Ileri, A.M., K\u00fclekci, M.O., and Xu, B. (2014, January 16\u201318). Shortest unique substring query revisited. Proceedings of the Symposium on Combinatorial Pattern Matching, Moscow, Russia.","DOI":"10.1007\/978-3-319-07566-2_18"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Tsuruta, K., Inenaga, S., Bannai, H., and Takeda, M. (2014). Shortest unique substrings queries in optimal time. Proceedings of the International Conference on Current Trends in Theory and Practice of Informatics, Springer.","DOI":"10.1007\/978-3-319-04298-5_44"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., and Cunial, F. (2014, January 20\u201322). Indexed matching statistics and shortest unique substrings. Proceedings of the International Symposium on String Processing and Information Retrieval, Ouro Preto, Brazil.","DOI":"10.1007\/978-3-319-11918-2_18"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.tcs.2017.08.002","article-title":"Space\u2013time trade-offs for finding shortest unique substrings and maximal unique matches","volume":"700","author":"Ganguly","year":"2017","journal-title":"Theor. Comput. Sci."},{"key":"ref_10","unstructured":"Senanayaka, S.B. (2019). Sub-linear Algorithms for Shortest Unique Substring and Maximal Unique Matches. [Master\u2019s Thesis, University of Wisconsin]."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Thankachan, S.V., and Xu, B. (2015, January 9\u201311). An in-place framework for exact and approximate shortest unique substring queries. Proceedings of the International Symposium on Algorithms and Computation, Nagoya, Japan.","DOI":"10.1007\/978-3-662-48971-0_63"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Allen, D.R., Thankachan, S.V., and Xu, B. (2020). An Ultra-Fast and Parallelizable Algorithm for Finding k-Mismatch Shortest Unique Substrings. IEEE\/ACM Trans. Comput. Biol. Bioinform.","DOI":"10.1109\/TCBB.2020.2968531"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Schultz, D.W., and Xu, B. (2020). Parallel Methods for Finding k-Mismatch Shortest Unique Substrings Using GPU. IEEE\/ACM Trans. Comput. Biol. Bioinform.","DOI":"10.1109\/TCBB.2019.2935061"},{"key":"ref_14","unstructured":"Golan, S., and Porat, E. (2017, January 4\u20136). Real-time streaming multi-pattern search for constant alphabet. Proceedings of the 25th Annual European Symposium on Algorithms (ESA 2017), Vienna, Austria."},{"key":"ref_15","unstructured":"Gawrychowski, P., and Starikovskaya, T. (2019, January 18\u201320). Streaming Dictionary Matching with Mismatches. Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), Pisa, Italy."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0304-3975(85)90157-4","article-title":"The Smallest Automaton Recognizing the Subwords of a Text","volume":"40","author":"Blumer","year":"1985","journal-title":"Theor. Comput. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1145\/116825.116845","article-title":"Two-Way String Matching","volume":"38","author":"Crochemore","year":"1991","journal-title":"J. ACM"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Weiner, P. (1973, January 15\u201317). Linear Pattern Matching Algorithms. Proceedings of the 14th Annual Symposium on Switching and Automata Theory, Iowa City, IA, USA.","DOI":"10.1109\/SWAT.1973.13"},{"key":"ref_19","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_20","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"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/234\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:11:08Z","timestamp":1760177468000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/234"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,18]]},"references-count":20,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["a13090234"],"URL":"https:\/\/doi.org\/10.3390\/a13090234","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,9,18]]}}}