The DOI matches its Crossref record; 5 of the 5 references it cites were found in a registry or an index.
Linear pattern matching algorithms
Abstract
In 1970, Knuth, Pratt, and Morris [1] showed how to do basic pattern matching in linear time. Related problems, such as those discussed in [4], have previously been solved by efficient but sub-optimal algorithms. In this paper, we introduce an interesting data structure called a bi-tree. A linear time algorithm for obtaining a compacted version of a bi-tree associated with a given string is presented. With this construction as the basic tool, we indicate how to solve several pattern matching problems, including some from [4] in linear time.
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
Kenny, A. (2018) · Carl Strehlow’s 1909 Comparative Heritage Dictionary: An Aranda, German, Loritja and Dieri to English Dictionary with Introductory Essays · doi:10.22459/cschd.08.2018.04 · Cited by 3,216
Jacob, M. (1989) · Health Education Journal · doi:10.1177/001789698904800401 · Cited by 3,090
The Art of Computer Programming. Volume 1: Fundamental Algorithms.
Odeh, R. E., & Knuth, D. E. (1969) · Journal of the American Statistical Association · doi:10.2307/2283757 · Cited by 2,525
The Art of Computer Programming
Worlton, W. J. (1968) · Nuclear Science and Engineering · doi:10.13182/nse68-a19548 · Cited by 2,251
Rapid identification of repeated patterns in strings, trees and arrays
Karp, R. M., Miller, R. E., & Rosenberg, A. L. (1972) · Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72 · doi:10.1145/800152.804905 · Cited by 274
Cited by
Versatile and open software for comparing large genomes
Kurtz, S., Phillippy, A., Delcher, A. L., Smoot, M., Shumway, M., Antonescu, C., & Salzberg, S. L. (2004) · Genome Biology · doi:10.1186/gb-2004-5-2-r12 · Cited by 5,254
A guided tour to approximate string matching
Navarro, G. (2001) · ACM Computing Surveys · doi:10.1145/375360.375365 · Cited by 2,561
A Space-Economical Suffix Tree Construction Algorithm
McCreight, E. M. (1976) · Journal of the ACM · doi:10.1145/321941.321946 · Cited by 1,511
On-line construction of suffix trees
Ukkonen, E. (1995) · Algorithmica · doi:10.1007/bf01206331 · Cited by 1,472
Web document clustering: a feasibility demonstration
Zamir, O., & Etzioni, O. (1998) · Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/290941.290956 · Cited by 1,055
Metadata
- Authors
- Weiner, P.
- Venue
- 14th Annual Symposium on Switching and Automata Theory (swat 1973)
- Publisher
- IEEE
- Published
- 1973-10
- Pages
- 1-11
- ISSN
- 0272-4847 (ISSN-L)
- OpenAlex
- W2533248932
- Cited by
- 1,801
- References
- 5
- FWCI
- 2.32
- Type
- conference paper
- 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.