The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
A fast string searching algorithm
Abstract
An algorithm is presented that searches for the location, “ i l” of the first occurrence of a character string, “ pat ,” in another string, “ string .” During the search operation, the characters of pat are matched starting with the last character of pat . The information gained by starting the match at the end of the pattern often allows the algorithm to proceed in large jumps through the text being searched. Thus the algorithm has the unusual property that, in most cases, not all of the first i characters of string are inspected. The number of characters actually inspected (on the average) decreases as a function of the length of pat . For a random English pattern of length 5, the algorithm will typically inspect i /4 characters of string before finding a match at i . Furthermore, the algorithm has been implemented so that (on the average) fewer than i + patlen machine instructions are executed. These conclusions are supported with empirical evidence and a theoretical analysis of the average behavior of the algorithm. The worst case behavior of the algorithm is linear in i + patlen , assuming the availability of array space for tables linear in patlen plus the size of the alphabet.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Efficient string matching: an aid to bibliographic search
Aho, A. V., & Corasick, M. J. (1975) · Communications of the ACM · doi:10.1145/360825.360855 · Cited by 2,944
Fast Pattern Matching in Strings
Knuth, D. E., Morris, Jr., & Pratt, V. R. (1977) · SIAM Journal on Computing · doi:10.1137/0206024 · Cited by 2,936
Cited by
A guided tour to approximate string matching
Navarro, G. (2001) · ACM Computing Surveys · doi:10.1145/375360.375365 · Cited by 2,561
GMAP: A genomic mapping and alignment program for mRNA and EST sequences
Wu, T. D., & Watanabe, C. K. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bti310 · Cited by 2,354
Intrusion detection system: A comprehensive review
Liao, H.-J., Richard Lin, C.-H., Lin, Y.-C., & Tung, K.-Y. (2013) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2012.09.004 · Cited by 1,630
Efficient randomized pattern-matching algorithms
Karp, R. M., & Rabin, M. O. (1987) · IBM Journal of Research and Development · doi:10.1147/rd.312.0249 · Cited by 1,269
Bland, C., Ramsey, T. L., Sabree, F., Lowe, M., Brown, K., Kyrpides, N. C., & Hugenholtz, P. (2007) · BMC Bioinformatics · doi:10.1186/1471-2105-8-209 · Cited by 1,049
(1998) · Choice Reviews Online · doi:10.5860/choice.35-6287 · Cited by 904
Accurate, scalable in-network identification of p2p traffic using application signatures
Sen, S., Spatscheck, O., & Wang, D. (2004) · Proceedings of the 13th international conference on World Wide Web · doi:10.1145/988672.988742 · Cited by 807
The Botany Array Resource: e‐Northerns, Expression Angling, and promoter analyses
Toufighi, K., Brady, S. M., Austin, R., Ly, E., & Provart, N. J. (2005) · The Plant Journal · doi:10.1111/j.1365-313x.2005.02437.x · Cited by 763
Fast text searching: allowing errors
Wu, S., & Manber, U. (1992) · Communications of the ACM · doi:10.1145/135239.135244 · Cited by 727
Data compression via textual substitution
Storer, J. A., & Szymanski, T. G. (1982) · Journal of the ACM · doi:10.1145/322344.322346 · Cited by 634
A new approach to text searching
Baeza-Yates, R., & Gonnet, G. H. (1992) · Communications of the ACM · doi:10.1145/135239.135243 · Cited by 603
Practical fast searching in strings
Horspool, R. N. (1980) · Software: Practice and Experience · doi:10.1002/spe.4380100608 · Cited by 594
Hall, P. A. V., & Dowling, G. R. (1980) · ACM Computing Surveys · doi:10.1145/356827.356830 · Cited by 586
A very fast substring search algorithm
Sunday, D. M. (1990) · Communications of the ACM · doi:10.1145/79173.79184 · Cited by 387
Early application identification
Bernaille, L., Teixeira, R., & Salamatian, K. (2006) · Proceedings of the 2006 ACM CoNEXT conference on - CoNEXT '06 · doi:10.1145/1368436.1368445 · Cited by 374
“Payload analysis tools rely on substring matching algorithms [7].”
MethodAlgorithms for Finding Patterns in Strings
AHO, A. V. (1990) · Algorithms and Complexity · doi:10.1016/b978-0-444-88071-0.50010-2 · Cited by 373
The smallest automation recognizing the subwords of a text
Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M. T., & Seiferas, J. (1985) · Theoretical Computer Science · doi:10.1016/0304-3975(85)90157-4 · Cited by 334
Fast parallel and serial approximate string matching
Landau, G. M., & Vishkin, U. (1989) · Journal of Algorithms · doi:10.1016/0196-6774(89)90010-2 · Cited by 328
Tutorial notes on partial evaluation
Consel, C., & Danvy, O. (1993) · Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '93 · doi:10.1145/158511.158707 · Cited by 316
Recent Named Entity Recognition and Classification techniques: A systematic review
Goyal, A., Gupta, V., & Kumar, M. (2018) · Computer Science Review · doi:10.1016/j.cosrev.2018.06.001 · Cited by 309
Navarro, G., & Raffinot, M. (2002) · Cambridge University Press eBooks · doi:10.1017/cbo9781316135228 · Cited by 291
A systematic literature review for network intrusion detection system (IDS)
Abdulganiyu, O. H., Ait Tchakoucht, T., & Saheed, Y. K. (2023) · International Journal of Information Security · doi:10.1007/s10207-023-00682-2 · Cited by 279
Hazay, C., & Lindell, Y. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78524-8_10 · Cited by 267
Quantum Pattern Matching Fast on Average
Montanaro, A. (2017) · Algorithmica · doi:10.1007/s00453-015-0060-4 · Cited by 84
“As well as the KMP algorithm already mentioned, another approach frequently used in practice classically is the Boyer-Moore algorithm [5], which achieves good performance for random inputs when the alphabet size is large.”
MethodOn-line string matching algorithms: survey and experimental results
Michailidis, P. D., & Margaritis, K. G. (2001) · International Journal of Computer Mathematics · doi:10.1080/00207160108805036 · Cited by 53
Mao, Y., Fisher, D. W., Yang, S., Keszycki, R. M., & Dong, H. (2020) · PLOS ONE · doi:10.1371/journal.pone.0226021 · Cited by 28
Innovative Automation Algorithm in Micro-multinational Data-Entry Industry
Faruqui, N., Yousuf, M. A., Chakraborty, P., & Hossain, M. S. (2020) · Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-030-52856-0_54 · Cited by 21
Implementation Issues of Early Application Identification
Bernaille, L., & Teixeira, R. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-76809-8_14 · Cited by 11
Metadata
- Authors
- Boyer, R. S., & Moore, J. S.
- Venue
- Communications of the ACM
- Published
- 1977-10
- Volume
- 20
- Issue
- 10
- Pages
- 762-772
- ISSN
- 0001-0782 (ISSN-L)
- 1557-7317
- OpenAlex
- W2134826720
- Cited by
- 2,290
- References
- 2
- FWCI
- 17.39
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.