{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:27:45Z","timestamp":1760243265086,"version":"build-2065373602"},"reference-count":22,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2014,6,23]],"date-time":"2014-06-23T00:00:00Z","timestamp":1403481600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We present the FQS (faster quick search) algorithm, an improved variation of the quick search algorithm. The quick search (QS) exact pattern matching algorithm and its variants are among the fastest practical matching algorithms today. The FQS algorithm computes a statistically expected shift value, which allows maximal shifts and a smaller number of comparisons between the pattern and the text. Compared to the state-of-the-art QS variants of exact pattern matching algorithms, the proposed FQS algorithm is the fastest when l\u03a3l \u2264 128, where l\u03a3l is the alphabet size. FQS also has a competitive running time when l\u03a3l &gt; 128. Running on three practical text files, E. coli (l\u03a3l  = 4), Bible (l\u03a3l  = 63) and World192 (l\u03a3l  = 94), FQS resulted in the best performance in practice. Our FQS algorithm will have important applications in the domain of genomic database searching, involving DNA or RNA sequence databases with four symbols \u03a3 = {A, C, G, T(\/U)} or protein databases with l\u03a3l = 20.<\/jats:p>","DOI":"10.3390\/a7020253","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T02:39:58Z","timestamp":1403577598000},"page":"253-275","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Faster Quick Search Algorithm"],"prefix":"10.3390","volume":"7","author":[{"given":"Jie","family":"Lin","sequence":"first","affiliation":[{"name":"Faculty of Software, Fujian Normal University, Fuzhou 350108, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donald","family":"Adjeroh","sequence":"additional","affiliation":[{"name":"Lane Department of Computer Science and Electrical Engineering, West Virginia University, Morgantown, WV 26506, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yue","family":"Jiang","sequence":"additional","affiliation":[{"name":"Faculty of Software, Fujian Normal University, Fuzhou 350108, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,6,23]]},"reference":[{"key":"ref_1","unstructured":"Charras, C., and Lecroq, T. (2004). Handbook of Exact String Matching Algorithms, College Publications."},{"key":"ref_2","unstructured":"Smyth, W. (2003). Computing Patterns in Strings, Addison-Wesley."},{"key":"ref_3","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_4","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_5","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1145\/359842.359859","article-title":"A fast string searching algorithm","volume":"20","author":"Boyer","year":"1977","journal-title":"Commun. ACM"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/135239.135243","article-title":"A new approach to text searching","volume":"35","author":"Gonnet","year":"1992","journal-title":"Commun. ACM"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1016\/j.jda.2008.09.001","article-title":"Average-optimal string matching","volume":"7","author":"Fredriksson","year":"2009","journal-title":"J. Discret. Algorithms"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1093\/comjnl\/bxt023","article-title":"Bit-Parallel Algorithms for Exact Circular String Matching","volume":"57","author":"Lee","year":"2014","journal-title":"Comput. J."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"13:1","DOI":"10.1145\/2431211.2431212","article-title":"The Exact Online String Matching Problem: A Review of the Most Recent Results","volume":"45","author":"Faro","year":"2013","journal-title":"ACM Comput. Surv."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1145\/79173.79184","article-title":"A Very Fast Substring Search Algorithm","volume":"33","author":"Sunday","year":"1990","journal-title":"Commun. ACM"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/0890-5401(91)90016-U","article-title":"Optimal Canonization of All Substrings of a String","volume":"95","author":"Apostolico","year":"1991","journal-title":"Inf. Comput."},{"key":"ref_12","unstructured":"Crochemore, M., and Rytter, W. (1994). Text Algorithms, Oxford University Press."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1016\/j.jda.2006.11.004","article-title":"A simple fast hybrid pattern-matching algorithm","volume":"5","author":"Franek","year":"2007","journal-title":"J. Discret. Algorithms"},{"key":"ref_14","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_15","doi-asserted-by":"crossref","unstructured":"Gusfield, D. (1997). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press.","DOI":"10.1017\/CBO9780511574931"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Adjeroh, D., Bell, T., and Mukherjee, A. (2008). The Burrows-Wheeler Transform: Data Compression, Suffix Arrays and Pattern Matching, Springer.","DOI":"10.1007\/978-0-387-78909-5"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1561\/2000000038","article-title":"Pattern Matching in Compressed Texts and Images","volume":"6","author":"Adjeroh","year":"2013","journal-title":"Found. Trends Signal Process."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1145\/359146.359148","article-title":"On improving the worst case running time of the Boyer-Moore string matching algorithm","volume":"22","author":"Galil","year":"1979","journal-title":"In Commun. ACM"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1137\/0215007","article-title":"The Boyer Moore Galil string searching strategies revisited","volume":"15","author":"Apostolico","year":"1986","journal-title":"SIAM J. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1251","DOI":"10.1021\/ci030463z","article-title":"A fast pattern matching algorithm","volume":"44","author":"Sheik","year":"2004","journal-title":"J. Chem. Inf. Comput."},{"key":"ref_21","first-page":"47","article-title":"TVSBS: A fast exact pattern matching algorithm for biological sequences","volume":"91","author":"Thathoo","year":"2006","journal-title":"Curr. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1002\/spe.4380221006","article-title":"Tuning the Boyer-Moore-Horspool String Searching Algorithm","volume":"22","author":"Raita","year":"1992","journal-title":"Softw. Pract. Exp."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/2\/253\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:12:51Z","timestamp":1760217171000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/2\/253"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,23]]},"references-count":22,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2014,6]]}},"alternative-id":["a7020253"],"URL":"https:\/\/doi.org\/10.3390\/a7020253","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2014,6,23]]}}}