65papers

exact string matching bibliography

[1]  J. H. Morris and V. R. Pratt. A linear pattern-matching algorithm. n.40, (1970).
[2]  R. S. Boyer and J. S. Moore. A fast string searching algorithm. Commun. ACM, vol.20, n.10, pp.762--772, (1977).
[3]  D. E. Knuth and J. H. Morris and V. R. Pratt. Fast pattern matching in strings. SIAM J. Comput., vol.6, n.1, pp.323--350, (1977).
[4]  R. N. Horspool. Practical fast searching in strings. Softw. Pract. Exp., vol.10, n.6, pp.501--506, (1980).
[5]  Z. Galil and J. Seiferas. Time-space optimal string matching. jcss, vol.26, n.3, pp.280--294, (1983).
[6]  A. Apostolico and R. Giancarlo. The Boyer-Moore-Galil string searching strategies revisited. SIAM J. Comput., vol.15, n.1, pp.98--105, (1986).
[7]  R. F. Zhu and T. Takaoka. On improving the average case of the Boyer-Moore string matching algorithm. J. Inform. Process., vol.10, n.3, pp.173--177, (1987).
[8]  R. M. Karp and M. O. Rabin. Efficient randomized pattern-matching algorithms. ibmjrd, vol.31, n.2, pp.249--260, (1987).
[9]  D. M. Sunday. A very fast substring search algorithm. Commun. ACM, vol.33, n.8, pp.132--142, (1990).
[10]  A. Hume and D. M. Sunday. Fast string searching. Softw. Pract. Exp., vol.21, n.11, pp.1221--1248, (1991).
[11]  L. Colussi. Correctness and efficiency of the pattern matching algorithms. Inf. Comput., vol.95, n.2, pp.225--251, (1991).
[12]  P. D. Smith. Experiments with a very fast substring search algorithm. Softw. Pract. Exp., vol.21, n.10, pp.1065--1074, (1991).
[13]  A. Apostolico and M. Crochemore. Optimal canonization of all substrings of a string. Inf. Comput., vol.95, n.1, pp.76--95, (1991).
[14]  M. Crochemore and D. Perrin. Two-way string-matching. J. Assoc. Comput. Mach., vol.38, n.3, pp.651--675, (1991).
[15]  R. Baeza-Yates and G. H. Gonnet. A new approach to text searching. Commun. ACM, vol.35, n.10, pp.74--82, ACM, New York, NY, USA, (1992).
[16]  Z. Galil and R. Giancarlo. On the exact complexity of string matching: upper bounds. SIAM J. Comput., vol.21, n.3, pp.407--437, (1992).
[17]  T. Lecroq. A variation on the Boyer-Moore algorithm. Theor. Comput. Sci., vol.92, n.1, pp.119--144, (1992).
[18]  M. Crochemore. String-matching on ordered alphabets. Theor. Comput. Sci., vol.92, n.1, pp.33--47, (1992).
[19]  T. Raita. Tuning the Boyer-Moore-Horspool string searching algorithm. Softw. Pract. Exp., vol.22, n.10, pp.879--884, (1992).
[20]  I. Simon. String matching algorithms and automata. Proceedings of the 1st South American Workshop on String Processing, pp.151--157, Universidade Federal de Minas Gerais, Brazil, (1993).
[21]  C. Hancart. Analyse exacte et en moyenne d'algorithmes de recherche d'un motif dans un texte. (1993).
[22]  M. Crochemore and A. Czumaj and L. Gcasieniec and S. Jarominek and T. Lecroq and W. Plandowski and W. Rytter. Speeding up two string matching algorithms. Algorithmica, vol.12, n.4/5, pp.247--267, (1994).
[23]  M. Crochemore and W. Rytter. Text algorithms. Oxford University Press, (1994).
[24]  L. Colussi. Fastest pattern matching in strings. J. Algorithms, vol.16, n.2, pp.163--189, (1994).
[25]  G. Navarro and M. Raffinot. A Bit-parallel Approach to Suffix Automata: Fast Extended String Matching. n.TR/DC--98--1, (1998).
[26]  C. Charras and T. Lecroq and J. D. Pehoushek. A Very Fast String Matching Algorithm for Small Alphabets and Long Patterns. Proceedings of the 9th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, n.1448, pp.55--64, Springer-Verlag, Berlin, rutgers, (1998).
[27]  C. Allauzen and M. Crochemore and M. Raffinot. Factor oracle: a new structure for pattern matching. SOFSEM'99, Theory and Practice of Informatics, Lecture Notes in Computer Science, n.1725, pp.291--306, Springer-Verlag, Berlin, Milovy, Czech Republic, (1999).
[28]  T. Berry and S. Ravindran. A fast string matching algorithm and experimental results. Proceedings of the Prague Stringology Club Workshop '99, pp.16--28, ctu, (1999).
[29]  C. Allauzen and M. Raffinot. Simple Optimal String Matching Algorithm. J. Algorithms, vol.36, pp.102-116, (2000).
[30]  G. Navarro and M. Raffinot. Fast and Flexible String Matching by Combining Bit-Parallelism and Suffix Automata. ACM J. Experimental Algorithmics, vol.5, pp.4, (2000).
[31]  T. H. Cormen and C. E. Leiserson and R. L. Rivest and C. Stein. Introduction to Algorithms. MIT Press, (2001).
[32]  D. Cantone and S. Faro. Fast-Search: a new efficient variant of the Boyer-Moore string matching algorithm. WEA 2003, Lecture Notes in Computer Science, vol.2647, pp.247--267, Springer-Verlag, Berlin, (2003).
[33]  H. Peltola and J. Tarhio. Alternative Algorithms for Bit-Parallel String Matching. Proceedings of the 10th International Symposium on String Processing and Information Retrieval SPIRE'03, Lecture Notes in Computer Science, vol.2857, pp.80--94, Springer-Verlag, Berlin, Manaus, Brazil, (2003).
[34]  M. Ahmed and M. Kaykobad and R. A. Chowdhury. A New String Matching Algorithm. Int. J. Comput. Math., vol.80, pp.825--834, (2003).
[35]  S. S. Sheik and S. K. Aggarwal and A. Poddar and N. Balakrishnan and K. Sekar. A fast pattern matching algorithm. J. Chem. Inf. Comput., vol.44, pp.1251--1256, (2004).
[36]  D. Cantone and S. Faro. Searching for a substring with constant extra-space complexity. Proc. of Third International Conference on Fun with algorithms, pp.118--131, (2004).
[37]  D. Cantone and S. Faro. Fast-Search Algorithms: New Efficient Variants of the Boyer-Moore Pattern-Matching Algorithm. J. Autom. Lang. Comb., vol.10, n.5/6, pp.589--608, (2005).
[38]  J. Holub and B. Durian. Talk: Fast variants of bit parallel approach to suffix automata. The Second Haifa Annual International Stringology Research Workshop of the Israeli Science Foundation, (2005).
[39]  K. Fredriksson and S. Grabowski. Practical and Optimal String Matching. SPIRE, Lecture Notes in Computer Science, vol.3772, pp.376--387, Springer-Verlag, Berlin, (2005).
[40]  L. He and B. Fang and J. Sui. The wide window string matching algorithm. Theor. Comput. Sci., vol.332, n.1-3, pp.391--404, Elsevier Science Publishers Ltd., Essex, UK, (2005).
[41]  R. Thathoo and A. Virmani and S. S. Lakshmi and N. Balakrishnan and K. Sekar. TVSBS: A Fast Exact Pattern Matching Algorithm for Biological Sequences. J. Indian Acad. Sci., Current Sci., vol.91, n.1, pp.47--53, (2006).
[42]  M. E. Nebel. Fast string matching by using probabilities: on an optimal mismatch variant of Horspool's algorithm. Theor. Comput. Sci., vol.359, n.1, pp.329--343, Elsevier Science Publishers Ltd., Essex, UK, (2006).
[43]  C. Liu and Y. Wang and D. Liu and D. Li. Two Improved Single Pattern Matching Algorithms. ICAT Workshops, pp.419--422, IEEE Computer Society, Hangzhou, China, (2006).
[44]  T. Lecroq. Fast exact string matching algorithms. ipl, vol.102, n.6, pp.229--235, Elsevier North-Holland, Inc., Amsterdam, The Netherlands, The Netherlands, (2007).
[45]  F. Franek and C. G. Jennings and W. F. Smyth. A simple fast hybrid pattern-matching algorithm. J. Discret. Algorithms, vol.5, pp.682--695, (2007).
[46]  M. A. Sustik and J. S. Moore. String Searching over Small Alphabets. Technical Report TR-07-62, Department of Computer Sciences, University of Texas at Austin, (2007).
[47]  A. Hudaib and R. Al-Khalid and D. Suleiman and M. Itriq and A. Al-Anani. A Fast Pattern Matching Algorithm with Two Sliding Windows (TSW). J. Comput. Sci., vol.4, n.5, pp.393--401, (2008).
[48]  M. O. Kulekci. A method to overcome computer word size limitation in bit-parallel pattern matching. Proceedings of the 19th International Symposium on Algorithms and Computation, ISAAC 2008, Lecture Notes in Computer Science, vol.5369, pp.496--506, Springer-Verlag, Berlin, Gold Coast, Australia, (2008).
[49]  S. Faro and T. Lecroq. Efficient Variants of the Backward-Oracle-Matching Algorithm. Proceedings of the Prague Stringology Conference 2008, pp.146--160, Czech Technical University in Prague, Czech Republic, (2008).
[50]  P. Kalsi and H. Peltola and J. Tarhio. Comparison of Exact String Matching Algorithms for Biological Sequences. Proceedings of the Second International Conference on Bioinformatics Research and Development, BIRD'08, Communications in Computer and Information Science, vol.13, pp.417-426, Springer-Verlag, Berlin, Vienna, Austria, (2008).
[51]  B. Durian and J. Holub and H. Peltola and J. Tarhio. Tuning BNDM with q-Grams. Proceedings of the Workshop on Algorithm Engineering and Experiments, ALENEX 2009, pp.29--37, SIAM, New York, New York, USA, (2009).
[52]  M. O. Kulekci. Filter Based Fast Matching of Long Patterns by Using SIMD Instructions. Proceedings of the Prague Stringology Conference 2009, pp.118--128, Czech Technical University in Prague, Czech Republic, (2009).
[53]  S. Deusdado and P. Carvalho. GRASPm: an efficient algorithm for exact pattern-matching in genomic sequences. Int. J. Bioinformatics Res. Appl., vol.5, n.4, pp.385--401, Inderscience Publishers, Inderscience Publishers, Geneva, SWITZERLAND, (2009).
[54]  K. Fredriksson. Succinct backward-DAWG-matching. J. Exp. Algorithmics, vol.13, pp.1.8--1.26, ACM, New York, NY, USA, (2009).
[55]  G. Zhang and E. Zhu and L. Mao and M. Yin. A Bit-Parallel Exact String Matching Algorithm for Small Alphabet. Proceedings of the Third International Workshop on Frontiers in Algorithmics, FAW 2009, Hefei, China, Lecture Notes in Computer Science, vol.5598, pp.336--345, Springer-Verlag, Berlin, (2009).
[56]  H. Fan and N. Yao and H. Ma. Fast Variants of the Backward-Oracle-Marching Algorithm. Proceedings of the 2009 Fourth International Conference on Internet Computing for Science and Engineering, ICICSE '09, pp.56--59, IEEE Computer Society, Washington, DC, USA, (2009).
[57]  D. Cantone and S. Faro and E. Giaquinta. A Compact Representation of Nondeterministic (Suffix) Automata for the Bit-Parallel Approach. Combinatorial Pattern Matching, Lecture Notes in Computer Science, vol.6129, pp.288--298, Springer-Verlag, Berlin, (2010).
[58]  D. Cantone and S. Faro and E. Giaquinta. Bit-Parallelism^2: Getting to the Next Level of Parallelism. Fun with Algorithms, Lecture Notes in Computer Science, vol.6099, pp.166--177, Springer-Verlag, Berlin, (2010).
[59]  B. Durian and H. Peltola and L. Salmela and J. Tarhio. Bit-Parallel Search Algorithms for Long Patterns. Experimental Algorithms - 9th International Symposium, SEA 2010, Lecture Notes in Computer Science, n.6049, pp.129--140, Springer-Verlag, Berlin, (2010).
[60]  H. Peltola and J. Tarhio. Variations of Forward-SBNDM. Proceedings of the Prague Stringology Conference '11, pp.3--14, Czech Technical University, Prague, Czech Republic, (2011).
[61]  S. Faro and M. O. Kulekci. Fast Multiple String Matching Using Streaming SIMD Extensions Technology. String Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Lecture Notes in Computer Science, n.7608, pp.217--228, Springer-Verlag, Berlin, (2012).
[62]  S. Faro and T. Lecroq. A Multiple Sliding Windows Approach to Speed Up String Matching Algorithms. Experimental Algorithms - 11th International Symposium, SEA 2012, Lecture Notes in Computer Science, n.7276, pp.172--183, Springer-Verlag, Berlin, (2012).
[63]  S. Faro and T. Lecroq. A Fast Suffix Automata Based Algorithm for Exact Online String Matching. Implementation and Application of Automata - 17th International Conference, CIAA 2012, Lecture Notes in Computer Science, n.7381, pp.149--158, Springer-Verlag, Berlin, (2012).
[64]  O. Ben-Kiki and P. Bille and D. Breslauer and L. Gasieniec and R. Grossi and O. Weimann. Optimal Packed String Matching. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011, LIPIcs, n.13, pp.423--432, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, (2012).
[65]  S. Faro and M. O. Kulekci. Fast Packed String Matching for Short Patterns. Meeting on Algorithm Engineering and Experiments, ALENEX 2013, (2013).