{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T01:37:04Z","timestamp":1772761024542,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,8,20]],"date-time":"2021-08-20T00:00:00Z","timestamp":1629417600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,20]],"date-time":"2021-08-20T00:00:00Z","timestamp":1629417600000},"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":["JP20J11983"],"award-info":[{"award-number":["JP20J11983"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18J10967"],"award-info":[{"award-number":["JP18J10967"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18K18002"],"award-info":[{"award-number":["JP18K18002"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17H01697"],"award-info":[{"award-number":["JP17H01697"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP16H02783"],"award-info":[{"award-number":["JP16H02783"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20H04141"],"award-info":[{"award-number":["JP20H04141"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18H04098"],"award-info":[{"award-number":["JP18H04098"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJPR1922"],"award-info":[{"award-number":["JPMJPR1922"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A substring <jats:italic>u<\/jats:italic> of a string <jats:italic>T<\/jats:italic> is called a <jats:italic>minimal unique substring<\/jats:italic>\u00a0(<jats:italic>MUS<\/jats:italic>) of <jats:italic>T<\/jats:italic> if <jats:italic>u<\/jats:italic> occurs exactly once in <jats:italic>T<\/jats:italic> and any proper substring of <jats:italic>u<\/jats:italic> occurs at least twice in <jats:italic>T<\/jats:italic>. In this paper, we study the problem of computing MUSs for a sliding window over a given string <jats:italic>T<\/jats:italic>. We first show how the set of MUSs can change when the window slides over <jats:italic>T<\/jats:italic>. We then present an <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n\\log \\sigma ')$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>\u03c3<\/mml:mi>\n                      <mml:mo>\u2032<\/mml:mo>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time and <jats:italic>O<\/jats:italic>(<jats:italic>d<\/jats:italic>)-space algorithm to compute MUSs for a sliding window of size <jats:italic>d<\/jats:italic> over the input string <jats:italic>T<\/jats:italic> of length <jats:italic>n<\/jats:italic>, where <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\sigma '\\le d$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mi>\u03c3<\/mml:mi>\n                      <mml:mo>\u2032<\/mml:mo>\n                    <\/mml:msup>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the maximum number of distinct characters in every window.<\/jats:p>","DOI":"10.1007\/s00453-021-00864-1","type":"journal-article","created":{"date-parts":[[2021,8,20]],"date-time":"2021-08-20T07:04:06Z","timestamp":1629443046000},"page":"670-693","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Computing Minimal Unique Substrings for a Sliding Window"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2922-9434","authenticated-orcid":false,"given":"Takuya","family":"Mieno","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuta","family":"Fujishige","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuto","family":"Nakashima","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hideo","family":"Bannai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,20]]},"reference":[{"key":"864_CR1","doi-asserted-by":"publisher","unstructured":"Abedin, P., Ganguly, A., Pissis, S.P., Thankachan, S.V.: Range shortest unique substring queries. In: Brisaboa, N.R., Puglisi, S.J. (eds.) String Processing and Information Retrieval\u201426th International Symposium, SPIRE 2019, Segovia, Spain, October 7-9, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11811, pp. 258\u2013266. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-32686-9_18","DOI":"10.1007\/978-3-030-32686-9_18"},{"key":"864_CR2","unstructured":"Akagi, T., Kuhara, Y., Mieno, T., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Combinatorics of minimal absent words for a sliding window. abs\/2105.08496 (2021). https:\/\/arxiv.org\/abs\/2105.08496"},{"key":"864_CR3","doi-asserted-by":"publisher","unstructured":"Belazzougui, D., Cunial, F.: Indexed matching statistics and shortest unique substrings. In: de\u00a0Moura, E.S., Crochemore, M. (eds.) String Processing and Information Retrieval\u201421st International Symposium, SPIRE 2014, Ouro Preto, Brazil, October 20\u201322, 2014. Proceedings, Lecture Notes in Computer Science, vol. 8799, pp. 179\u2013190. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-319-11918-2_18","DOI":"10.1007\/978-3-319-11918-2_18"},{"issue":"4","key":"864_CR4","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1109\/TCOM.1984.1096090","volume":"32","author":"JG Cleary","year":"1984","unstructured":"Cleary, J.G., Witten, I.H.: Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. 32(4), 396\u2013402 (1984). https:\/\/doi.org\/10.1109\/TCOM.1984.1096090","journal-title":"IEEE Trans. Commun."},{"key":"864_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2019.104461","author":"M Crochemore","year":"2020","unstructured":"Crochemore, M., H\u00e9liou, A., Kucherov, G., Mouchard, L., Pissis, S.P., Ramusat, Y.: Absent words in a sliding window with applications. Inf. Comput. (2020). https:\/\/doi.org\/10.1016\/j.ic.2019.104461","journal-title":"Inf. Comput."},{"issue":"4","key":"864_CR6","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1145\/63334.63341","volume":"32","author":"ER Fiala","year":"1989","unstructured":"Fiala, E.R., Greene, D.H.: Data compression with finite windows. Commun. ACM 32(4), 490\u2013505 (1989). https:\/\/doi.org\/10.1145\/63334.63341","journal-title":"Commun. ACM"},{"key":"864_CR7","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.tcs.2017.08.002","volume":"700","author":"A Ganguly","year":"2017","unstructured":"Ganguly, A., Hon, W., Shah, R., Thankachan, S.V.: Space-time trade-offs for finding shortest unique substrings and maximal unique matches. Theor. Comput. Sci. 700, 75\u201388 (2017). https:\/\/doi.org\/10.1016\/j.tcs.2017.08.002","journal-title":"Theor. Comput. Sci."},{"key":"864_CR8","doi-asserted-by":"publisher","unstructured":"Gr\u00e4f, S., Nielsen, F.G.G., Kurtz, S., Huynen, M.A., Birney, E., Stunnenberg, H., Flicek, P.: Optimized design and assessment of whole genome tiling arrays. In: Proceedings 15th International Conference on Intelligent Systems for Molecular Biology (ISMB) & 6th European Conference on Computational Biology (ECCB), Vienna, Austria, July 21\u201325, 2007, pp. 195\u2013204 (2007). https:\/\/doi.org\/10.1093\/bioinformatics\/btm200","DOI":"10.1093\/bioinformatics\/btm200"},{"key":"864_CR9","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1186\/1471-2105-6-123","volume":"6","author":"B Haubold","year":"2005","unstructured":"Haubold, B., Pierstorff, N., M\u00f6ller, F., Wiehe, T.: Genome comparison without alignment using shortest unique substrings. BMC Bioinform. 6, 123 (2005). https:\/\/doi.org\/10.1186\/1471-2105-6-123","journal-title":"BMC Bioinform."},{"key":"864_CR10","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.tcs.2017.05.032","volume":"690","author":"W Hon","year":"2017","unstructured":"Hon, W., Thankachan, S.V., Xu, B.: In-place algorithms for exact and approximate shortest unique substring problems. Theor. Comput. Sci. 690, 12\u201325 (2017). https:\/\/doi.org\/10.1016\/j.tcs.2017.05.032","journal-title":"Theor. Comput. Sci."},{"key":"864_CR11","doi-asserted-by":"publisher","unstructured":"Hu, X., Pei, J., Tao, Y.: Shortest unique queries on strings. In: de\u00a0Moura, E.S., Crochemore, M. (eds.) String Processing and Information Retrieval\u201421st International Symposium, SPIRE 2014, Ouro Preto, Brazil, October 20\u201322, 2014. Proceedings, Lecture Notes in Computer Science, vol. 8799, pp. 161\u2013172. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-319-11918-2_16","DOI":"10.1007\/978-3-319-11918-2_16"},{"key":"864_CR12","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1016\/j.tcs.2014.11.004","volume":"562","author":"AM Ileri","year":"2015","unstructured":"Ileri, A.M., K\u00fclekci, M.O., Xu, B.: A simple yet time-optimal and linear-space algorithm for shortest unique substring queries. Theor. Comput. Sci. 562, 621\u2013633 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2014.11.004","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20134","key":"864_CR13","doi-asserted-by":"publisher","first-page":"183","DOI":"10.3233\/FI-2011-536","volume":"110","author":"L Ilie","year":"2011","unstructured":"Ilie, L., Smyth, W.F.: Minimum unique substrings and maximum repeats. Fundam. Inform. 110(1\u20134), 183\u2013195 (2011). https:\/\/doi.org\/10.3233\/FI-2011-536","journal-title":"Fundam. Inform."},{"key":"864_CR14","unstructured":"Larsson, N.J.: Structures of string matching and data compression. Ph.D. thesis, Lund University, Sweden (1999). http:\/\/lup.lub.lu.se\/record\/19255"},{"issue":"11","key":"864_CR15","doi-asserted-by":"publisher","first-page":"1067","DOI":"10.1093\/bioinformatics\/17.11.1067","volume":"17","author":"F Li","year":"2001","unstructured":"Li, F., Stormo, G.D.: Selection of optimal DNA oligos for gene expression arrays. Bioinformatics 17(11), 1067\u20131076 (2001). https:\/\/doi.org\/10.1093\/bioinformatics\/17.11.1067","journal-title":"Bioinformatics"},{"key":"864_CR16","doi-asserted-by":"publisher","unstructured":"Mieno, T., Inenaga, S., Bannai, H., Takeda, M.: Shortest unique substring queries on run-length encoded strings. In: Faliszewski, P., Muscholl, A., Niedermeier, R. (eds.) 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22\u201326, 2016\u2014Krak\u00f3w, Poland, LIPIcs, vol.\u00a058, pp. 69:1\u201369:11. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2016.69","DOI":"10.4230\/LIPIcs.MFCS.2016.69"},{"key":"864_CR17","doi-asserted-by":"publisher","unstructured":"Mieno, T., K\u00f6ppl, D., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Compact data structures for shortest unique substring queries. In: Brisaboa, N.R., Puglisi, S.J. (eds.) String Processing and Information Retrieval\u201426th International Symposium, SPIRE 2019, Segovia, Spain, October 7\u20139, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11811, pp. 107\u2013123. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-32686-9_8","DOI":"10.1007\/978-3-030-32686-9_8"},{"key":"864_CR18","doi-asserted-by":"publisher","unstructured":"Mieno, T., Kuhara, Y., Akagi, T., Fujishige, Y., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Minimal unique substrings and minimal absent words in a sliding window. In: Chatzigeorgiou, A., Dondi, R., Herodotou, H., Kapoutsis, C.A., Manolopoulos, Y., Papadopoulos, G.A., Sikora, F. (eds.) SOFSEM 2020: Theory and Practice of Computer Science\u201446th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20\u201324, 2020, Proceedings, Lecture Notes in Computer Science, vol. 12011, pp. 148\u2013160. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-38919-2_13","DOI":"10.1007\/978-3-030-38919-2_13"},{"issue":"1","key":"864_CR19","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0304-3975(00)00436-9","volume":"273","author":"F Mignosi","year":"2002","unstructured":"Mignosi, F., Restivo, A., Sciortino, M.: Words and forbidden factors. Theor. Comput. Sci. 273(1), 99\u2013117 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"864_CR20","doi-asserted-by":"publisher","unstructured":"Pei, J., Wu, W.C., Yeh, M.: On shortest unique substring queries. In: Jensen, C.S., Jermaine, C.M., Zhou, X. (eds.) 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8\u201312, 2013, pp. 937\u2013948. IEEE Computer Society (2013). https:\/\/doi.org\/10.1109\/ICDE.2013.6544887","DOI":"10.1109\/ICDE.2013.6544887"},{"key":"864_CR21","unstructured":"Senft, M.: Suffix tree for a sliding window: An overview. In: WDS, vol.\u00a05, pp. 41\u201346. Matfyzpress (2005)"},{"key":"864_CR22","doi-asserted-by":"publisher","unstructured":"Tsuruta, K., Inenaga, S., Bannai, H., Takeda, M.: Shortest unique substrings queries in optimal time. In: Geffert, V., Preneel, B., Rovan, B., Stuller, J., Tjoa, A.M. (eds.) SOFSEM 2014: Theory and Practice of Computer Science\u201440th International Conference on Current Trends in Theory and Practice of Computer Science, Nov\u00fd Smokovec, Slovakia, January 26\u201329, 2014, Proceedings, Lecture Notes in Computer Science, vol. 8327, pp. 503\u2013513. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-319-04298-5_44","DOI":"10.1007\/978-3-319-04298-5_44"},{"issue":"3","key":"864_CR23","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14(3), 249\u2013260 (1995). https:\/\/doi.org\/10.1007\/BF01206331","journal-title":"Algorithmica"},{"issue":"13","key":"864_CR24","doi-asserted-by":"publisher","first-page":"2101","DOI":"10.1093\/bioinformatics\/bth210","volume":"20","author":"J Zheng","year":"2004","unstructured":"Zheng, J., Close, T.J., Jiang, T., Lonardi, S.: Efficient selection of unique and popular oligos for large EST databases. Bioinformatics 20(13), 2101\u20132112 (2004). https:\/\/doi.org\/10.1093\/bioinformatics\/bth210","journal-title":"Bioinformatics"},{"issue":"3","key":"864_CR25","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory 23(3), 337\u2013343 (1977). https:\/\/doi.org\/10.1109\/TIT.1977.1055714","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00864-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00864-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00864-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,15]],"date-time":"2022-03-15T09:04:35Z","timestamp":1647335075000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00864-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,20]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["864"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00864-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,20]]},"assertion":[{"value":"29 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}