{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T10:42:42Z","timestamp":1775644962152,"version":"3.50.1"},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2015,5,11]],"date-time":"2015-05-11T00:00:00Z","timestamp":1431302400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2017,2]]},"abstract":"<jats:p>Circular string matching is a problem which naturally arises in many contexts. It consists in finding all occurrences of the rotations of a pattern of length<jats:italic>m<\/jats:italic>in a text of length<jats:italic>n<\/jats:italic>. There exist optimal worst- and average-case algorithms for circular string matching. Here, we present a suboptimal average-case algorithm for circular string matching requiring time<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0960129515000134_inline1\"\/><jats:tex-math>$\\mathcal{O}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>(<jats:italic>n<\/jats:italic>) and space<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0960129515000134_inline1\"\/><jats:tex-math>$\\mathcal{O}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>(<jats:italic>m<\/jats:italic>). The importance of our contribution is underlined by the fact that the proposed algorithm can be easily adapted to deal with circular dictionary matching. In particular, we show how the circular dictionary-matching problem can be solved in average-case time<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0960129515000134_inline1\"\/><jats:tex-math>$\\mathcal{O}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>(<jats:italic>n<\/jats:italic>+<jats:italic>M<\/jats:italic>) and space<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0960129515000134_inline1\"\/><jats:tex-math>$\\mathcal{O}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>(<jats:italic>M<\/jats:italic>), where<jats:italic>M<\/jats:italic>is the total length of the dictionary patterns, assuming that the shortest pattern is sufficiently long. Moreover, the presented average-case algorithms and other worst-case approaches were also implemented. Experimental results, using real and synthetic data, demonstrate that the implementation of the presented algorithms can accelerate the computations by more than a factor of two compared to the corresponding implementation of other approaches.<\/jats:p>","DOI":"10.1017\/s0960129515000134","type":"journal-article","created":{"date-parts":[[2015,5,11]],"date-time":"2015-05-11T07:41:30Z","timestamp":1431330090000},"page":"143-156","source":"Crossref","is-referenced-by-count":6,"title":["Fast circular dictionary-matching algorithm"],"prefix":"10.1017","volume":"27","author":[{"given":"TANVER","family":"ATHAR","sequence":"first","affiliation":[]},{"given":"CARL","family":"BARTON","sequence":"additional","affiliation":[]},{"given":"WIDMER","family":"BLAND","sequence":"additional","affiliation":[]},{"given":"JIA","family":"GAO","sequence":"additional","affiliation":[]},{"given":"COSTAS S.","family":"ILIOPOULOS","sequence":"additional","affiliation":[]},{"given":"CHANG","family":"LIU","sequence":"additional","affiliation":[]},{"given":"SOLON P.","family":"PISSIS","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2015,5,11]]},"reference":[{"key":"S0960129515000134_ref24","volume-title":"Computing Patterns in Strings","author":"Smyth","year":"2003"},{"key":"S0960129515000134_ref23","doi-asserted-by":"publisher","DOI":"10.1137\/0205003"},{"key":"S0960129515000134_ref25","doi-asserted-by":"crossref","unstructured":"Weiner P. (1973). Linear pattern matching algorithms. In: Proceedings of the 14th Annual Symposium on Switching and Automata Theory (SWAT 1973), IEEE Computer Society 1\u201311.","DOI":"10.1109\/SWAT.1973.13"},{"key":"S0960129515000134_ref4","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-3-319-15579-1_6","volume-title":"Language and Automata Theory and Applications","author":"Barton","year":"2015"},{"key":"S0960129515000134_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16321-0_19"},{"key":"S0960129515000134_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.09.001"},{"key":"S0960129515000134_ref22","doi-asserted-by":"crossref","unstructured":"Nong G. , Zhang S. and Chan W. H. (2009). Linear suffix array construction by almost pure induced-sorting. In: Storer J. A. and Marcellin M. W. (eds.) Proceedings of the 2009 Data Compression Conference, DCC 09, Washington, DC, USA, IEEE Computer Society 193\u2013202.","DOI":"10.1109\/DCC.2009.42"},{"key":"S0960129515000134_ref26","doi-asserted-by":"publisher","DOI":"10.1145\/135239.135244"},{"key":"S0960129515000134_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77891-2_5"},{"key":"S0960129515000134_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38905-4_15"},{"key":"S0960129515000134_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"key":"S0960129515000134_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.11.019"},{"key":"S0960129515000134_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_69"},{"key":"S0960129515000134_ref10","doi-asserted-by":"publisher","DOI":"10.1137\/090779759"},{"key":"S0960129515000134_ref12","unstructured":"Frousios K. , Iliopoulos C. S. , Mouchard L. , Pissis S. P. and Tischler G. (2010). REAL: An efficient REad ALigner for next generation sequencing reads. In: Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology, BCB 10, USA, ACM 154\u2013159."},{"key":"S0960129515000134_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240244"},{"key":"S0960129515000134_ref3","doi-asserted-by":"publisher","DOI":"10.1186\/1748-7188-9-9"},{"key":"S0960129515000134_ref21","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"S0960129515000134_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13509-5_9"},{"key":"S0960129515000134_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2010.08.004"},{"key":"S0960129515000134_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107341005"},{"key":"S0960129515000134_ref1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"S0960129515000134_ref2","unstructured":"Barton C. , Iliopoulos C. S. and Pissis S. P. (2013). Circular string matching revisited. In: Proceedings of the 4th Italian Conference on Theoretical Computer Science (ICTCS 2013) 200\u2013205."},{"key":"S0960129515000134_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.022"},{"key":"S0960129515000134_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22300-6_32"},{"key":"S0960129515000134_ref7","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxt023"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129515000134","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T09:47:46Z","timestamp":1691660866000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129515000134\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,11]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["S0960129515000134"],"URL":"https:\/\/doi.org\/10.1017\/s0960129515000134","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,11]]}}}