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
(1998) · Choice Reviews Online · doi:10.5860/choice.35-6287 · Cited by 904
Delcher, A. L., Kasif, S., Fleischmann, R. D., Peterson, J., White, O., & Salzberg, S. L. (1999) · Nucleic Acids Research · doi:10.1093/nar/27.11.2369 · Cited by 893
Navarro, G., & Mäkinen, V. (2007) · ACM Computing Surveys · doi:10.1145/1216370.1216372 · Cited by 735
Grouper: a dynamic clustering interface to Web search results
Zamir, O., & Etzioni, O. (1999) · Computer Networks · doi:10.1016/s1389-1286(99)00054-7 · Cited by 720
Replacing suffix trees with enhanced suffix arrays
Abouelhoda, M. I., Kurtz, S., & Ohlebusch, E. (2004) · Journal of Discrete Algorithms · doi:10.1016/s1570-8667(03)00065-0 · Cited by 668
Data compression via textual substitution
Storer, J. A., & Szymanski, T. G. (1982) · Journal of the ACM · doi:10.1145/322344.322346 · Cited by 634
STREME: accurate and versatile sequence motif discovery
Bailey, T. L. (2021) · Bioinformatics · doi:10.1093/bioinformatics/btab203 · Cited by 622
The Complexity of Some Problems on Subsequences and Supersequences
Maier, D. (1978) · Journal of the ACM · doi:10.1145/322063.322075 · Cited by 616
Approximate string-matching with q-grams and maximal matches
Ukkonen, E. (1992) · Theoretical Computer Science · doi:10.1016/0304-3975(92)90143-4 · Cited by 605
Honeycomb: creating intrusion detection signatures using honeypots
Kreibich, C., & Crowcroft, J. (2004) · ACM SIGCOMM Computer Communication Review · doi:10.1145/972374.972384 · Cited by 523
Optimal suffix tree construction with large alphabets
Farach, M. (2002) · Proceedings 38th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646102 · Cited by 443
Graph kernels for chemical informatics
Ralaivola, L., Swamidass, S. J., Saigo, H., & Baldi, P. (2005) · Neural Networks · doi:10.1016/j.neunet.2005.07.009 · Cited by 442
Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
Grossi, R., & Vitter, J. S. (2005) · SIAM Journal on Computing · doi:10.1137/s0097539702402354 · Cited by 431
Finding surprising patterns in a time series database in linear time and space
Keogh, E., Lonardi, S., & Chiu, B. '.-C. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775128 · Cited by 404
Simple Linear Work Suffix Array Construction
Kärkkäinen, J., & Sanders, P. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-45061-0_73 · Cited by 404
Algorithms 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
An algorithm for finding signals of unknown length in DNA sequences
Pavesi, G., Mauri, G., & Pesole, G. (2001) · Bioinformatics · doi:10.1093/bioinformatics/17.suppl_1.s207 · Cited by 337
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
Reducing the space requirement of suffix trees
Kurtz, S. (1999) · Software: Practice and Experience · doi:10.1002/(sici)1097-024x(199911)29:13<1149::aid-spe274>3.0.co;2-o · Cited by 334
SeqAn An efficient, generic C++ library for sequence analysis
Döring, A., Weese, D., Rausch, T., & Reinert, K. (2008) · BMC Bioinformatics · doi:10.1186/1471-2105-9-11 · Cited by 333
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
The string B-tree: a new data structure for string search in external memory and its applications
Ferragina, P., & Grossi, R. (1999) · Journal of the ACM · doi:10.1145/301970.301973 · Cited by 317
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
High-throughput sequence alignment using Graphics Processing Units
Schatz, M. C., Trapnell, C., Delcher, A. L., & Varshney, A. (2007) · BMC Bioinformatics · doi:10.1186/1471-2105-8-474 · Cited by 310
Deduplicating Training Data Makes Language Models Better
Lee, K., Ippolito, D., Nystrom, A., Zhang, C., Eck, D., Callison-Burch, C., & Carlini, N. (2022) · Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2022.acl-long.577 · Cited by 304
Fast Kernels for String and Tree Matching
Vishwanathan, S. V. N., & Smola, A. J. (2004) · Kernel Methods in Computational Biology · doi:10.7551/mitpress/4057.003.0008 · Cited by 294
Suffix arrays: a new method for on-line string searches
Manber, U., & Myers, E. W. (1990) · doi:10.5555/320176.320218 · Cited by 293
The Myriad Virtues of Subword Trees
Apostolico, A. (1985) · Combinatorial Algorithms on Words · doi:10.1007/978-3-642-82456-2_6 · Cited by 274
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
Farruggia, A., Gagie, T., Navarro, G., Puglisi, S. J., & Sirén, J. (2018) · The Computer Journal · doi:10.1093/comjnl/bxx108 · Cited by 14
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.