×

Speeding up two string-matching algorithms. (English) Zbl 0942.68574


MSC:

68Q25 Analysis of algorithms and problem complexity
68W10 Parallel algorithms in computer science
68R05 Combinatorics in computer science
68U15 Computing methodologies for text processing; mathematical typography
68P20 Information storage and retrieval of data
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. V. Aho, Algorithms for finding patterns in strings, inHandbook of Theoretical Computer Science, vol. A (J. van Leeuwen, ed.), Elsevier, Amsterdam, 1990, pp. 255–300. · Zbl 0900.68249
[2] A. Apostolico, The myriad virtues of suffix trees, inCombinatorial Algorithms on Words (A. Apostolico and Z. Galil, eds.), NATO Advanced Science Institutes, Series F, vol. 12, Springer-Verlag, Berlin, 1985, pp. 85–96.
[3] A. Apostolico and R. Giancarlo, The Boyer-Moore-Galil string searching strategies revisited,SIAM J. Comput. 15 (1986), 98–105. · Zbl 0589.68047 · doi:10.1137/0215007
[4] R. A. Baeza-Yates and M. Régnier, Average running time of the Boyer-Moore-Horspool algorithm,Theoret. Comput. Sci. 92(1) (1992), 19–31. · Zbl 0747.68020 · doi:10.1016/0304-3975(92)90133-Z
[5] L. Banachowski, A. Kreczmar, and W. Rytter,Analysis of Algorithms and Data Structures, Addison-Wesley, Reading, MA, 1991. · Zbl 0748.68028
[6] A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, M. T. Chen, and J. Seiferas, The smallest automaton recognizing the subwords of a text,Theoret. Comput. Sci. 40 (1985), 31–55. · Zbl 0574.68070 · doi:10.1016/0304-3975(85)90157-4
[7] R. S. Boyer and J. S. Moore, A fast string searching algorithm,Comm. ACM 20 (1977), 762–772. · Zbl 1219.68165 · doi:10.1145/359842.359859
[8] R. Cole, Tight bounds on the complexity of the Boyer-Moore pattern matching algorithm,Proceedings of the 2nd Annual ACM Symposium on Discrete Algorithms, 1990, pp. 224–233. · Zbl 0800.68505
[9] M. Crochemore, Transducers and repetitions,Theoret. Comput. Sci. 45 (1986), 63–86. · Zbl 0615.68053 · doi:10.1016/0304-3975(86)90041-1
[10] Z. Galil, On improving the worst case running time of the Boyer-Moore string searching algorithm,Comm. ACM 22 (1979), 505–508. · Zbl 0413.68041 · doi:10.1145/359146.359148
[11] L. J. Guibas and A. M. Odlyzko, A new proof of the linearity of the Boyer-Moore string searching algorithm,SIAM J. Comput. 9 (1980), 672–682. · Zbl 0446.68050 · doi:10.1137/0209051
[12] R. N. Horspool, Practical fast searching in strings,Software–Practice and Experience,10 (1980), 501–506. · doi:10.1002/spe.4380100608
[13] A. Hume and D. M. Sunday, Fast string searching,Software–Practice and Experience 21(11) (1991), 1221–1248. · doi:10.1002/spe.4380211105
[14] D. E. Knuth, J. H. Morris Jr and V. R. Pratt, Fast pattern matching in strings,SIAM J. Comput. 6 (1977), 323–350. · Zbl 0372.68005 · doi:10.1137/0206024
[15] T. Lecroq, A variation on Boyer-Moore algorithm,Theoret. Comput. Sci. 92 (1992), 119–144. · Zbl 0747.68023 · doi:10.1016/0304-3975(92)90139-7
[16] W. Rytter, A correct preprocessing algorithm for Boyer-Moore string searching,SIAM J. Comput. 9 (1980), 509–512. · Zbl 0446.68049 · doi:10.1137/0209037
[17] A. C. Yao, The complexity of pattern matching for a random string,SIAM J. Comput. 8 (1979), 368–387. · Zbl 0421.68045 · doi:10.1137/0208029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.