{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:36:36Z","timestamp":1760240196203,"version":"build-2065373602"},"reference-count":15,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T00:00:00Z","timestamp":1554681600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A multi-track string is a tuple of strings of the same length. Given the pattern and text of two multi-track strings, the permuted pattern matching problem is to find the occurrence positions of all permutations of the pattern in the text. In this paper, we propose several algorithms for permuted pattern matching. Our first algorithm, which is based on the Knuth\u2013Morris\u2013Pratt (KMP) algorithm, has a fast theoretical computing time with     O ( m k )     as the preprocessing time and     O ( n k log \u03c3 )     as the matching time, where n, m, k,    \u03c3   , and    occ    denote the length of the text, the length of the pattern, the number of strings in the multi-track, the alphabet size, and the number of occurrences of the pattern, respectively. We then improve the KMP-based algorithm by using an automaton, which has a better experimental running time. The next proposed algorithms are based on the Boyer\u2013Moore algorithm and the Horspool algorithm that try to perform pattern matching. These algorithms are the fastest experimental algorithms. Furthermore, we propose an extension of the AC-automaton algorithm that can solve dictionary matching on multi-tracks, which is a task to find multiple multi-track patterns in a multi-track text. Finally, we propose filtering algorithms that can perform permuted pattern matching quickly in practice.<\/jats:p>","DOI":"10.3390\/a12040073","type":"journal-article","created":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T11:54:52Z","timestamp":1554724492000},"page":"73","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Permuted Pattern Matching Algorithms on Multi-Track Strings"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8168-7312","authenticated-orcid":false,"given":"Diptarama","family":"Hendrian","sequence":"first","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Miyagi 980-8579, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yohei","family":"Ueki","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Miyagi 980-8579, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuyuki","family":"Narisawa","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Miyagi 980-8579, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5175-465X","authenticated-orcid":false,"given":"Ryo","family":"Yoshinaka","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Miyagi 980-8579, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ayumi","family":"Shinohara","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Miyagi 980-8579, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,4,8]]},"reference":[{"key":"ref_1","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_2","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_3","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1002\/spe.4380100608","article-title":"Practical fast searching in strings","volume":"10","author":"Horspool","year":"1980","journal-title":"Softw. Pract. Exp."},{"key":"ref_4","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 (SWAT 1973), Iowa City, IA, USA.","DOI":"10.1109\/SWAT.1973.13"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix Arrays: A New Method for On-Line String Searches","volume":"22","author":"Manber","year":"1993","journal-title":"SIAM J. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.jda.2010.12.001","article-title":"Position heaps: A simple and dynamic text indexing data structure","volume":"9","author":"Ehrenfeucht","year":"2011","journal-title":"J. Discret. Algorithms"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Katsura, T., Narisawa, K., Shinohara, A., Bannai, H., and Inenaga, S. (2013, January 26\u201331). Permuted Pattern Matching on Multi-track Strings. Proceedings of the SOFSEM 2013: 39th International Conference on Current Trends in Theory and Practice of Computer Science, \u0160pindler\u016fv Ml\u00fdn, Czech Republic.","DOI":"10.1007\/978-3-642-35843-2_25"},{"key":"ref_8","unstructured":"Katsura, T., Otomo, Y., Narisawa, K., and Shinohara, A. (2015, January 24\u201329). Position Heaps for Permuted Pattern Matching on Multi-Track Strings. Proceedings of the Student Research Forum Papers and Posters at SOFSEM 2015, Pec pod Snezkou, Czech Republic."},{"key":"ref_9","first-page":"37","article-title":"Filtering Multi-set Tree: Data Structure for Flexible Matching Using Multi-track Data","volume":"21","author":"Narisawa","year":"2015","journal-title":"Interdiscip. Inf. Sci."},{"key":"ref_10","unstructured":"Diptarama, Y.U., Narisawa, K., and Shinohara, A. (2016, January 23\u201328). KMP based pattern matching algorithms for multi-track strings. Proceedings of the Student Research Forum Papers and Posters at SOFSEM 2016, Harrachov, Czech Republic."},{"key":"ref_11","unstructured":"Diptarama, Y.U., Yoshinaka, R., and Shinohara, A. (2016, January 29\u201331). Fast Full Permuted Pattern Matching Algorithms on Multi-track Strings. Proceedings of the Prague Stringology Conference 2016, Prague, Czech Republic."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/j.tcs.2016.02.017","article-title":"Generalized pattern matching and periodicity under substring consistent equivalence relations","volume":"656","author":"Matsuoka","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","article-title":"Efficient string matching: An aid to bibliographic search","volume":"18","author":"Aho","year":"1975","journal-title":"Commun. ACM"},{"key":"ref_14","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_15","doi-asserted-by":"crossref","unstructured":"Indyk, P., and Motwani, R. (1998, January 24\u201326). Approximate nearest neighbors: Towards removing the curse of dimensionality. Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing\u2014STOC \u201998, Dallas, TX, USA.","DOI":"10.1145\/276698.276876"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/4\/73\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:43:42Z","timestamp":1760186622000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/4\/73"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,8]]},"references-count":15,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2019,4]]}},"alternative-id":["a12040073"],"URL":"https:\/\/doi.org\/10.3390\/a12040073","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,4,8]]}}}