# Linear Pattern Matching Algorithms

@inproceedings{Weiner1973LinearPM, title={Linear Pattern Matching Algorithms}, author={Peter Weiner}, booktitle={SWAT}, year={1973} }

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… Expand

#### 1,956 Citations

Linear pattern matching of repeated substrings

- Computer Science
- SIGA
- 1994

This paper attempts to explain Weiner’s result in a more accessible manner and describes familiar objects such as trees and other data structures described using notation drawn from automata theory. Expand

A simple fast hybrid pattern-matching algorithm

- Computer Science
- J. Discrete Algorithms
- 2007

A simple algorithm is described that employs the main ideas of KMP and BM and is among the fastest exact pattern-matching algorithms discovered to date, apparently dominant for alphabet size above 15-20. Expand

A Simple Fast Hybrid Pattern-Matching Algorithm

- Computer Science
- CPM
- 2005

A simple algorithm is described that employs the main ideas of KMP and BM in an effort to combine these desirable features, and experiments indicate that in practice the new algorithm is among the fastest exact pattern-matching algorithms discovered to date. Expand

Efficient tree pattern matching

- Mathematics, Computer Science
- 30th Annual Symposium on Foundations of Computer Science
- 1989

An O(nM/sup 0.75/ polylog(m))-step algorithm for tree pattern matching problem is designed and the problems of linear string matching with don't care symbols and linear string max-min convolution are treated. Expand

Simple Optimal Parallel Multiple Pattern Matching

- Computer Science, Mathematics
- J. Algorithms
- 2000

This paper presents a simple algorithm for solving the multipattern matching problem, with optimal speedup, and the sequential version of the algorithm derived by slowing down the parallel design yields a new and simple (linear-time) algorithm for string matching. Expand

2 Predecessor Problem 2.1 Tries and Compressed Tries

- 2012

In this lecture, we consider the string matching problem finding some or all places in a text where the query string occurs as a substring. From the perspective of a one-shot approach, we can solve… Expand

Two-way string-matching

- Mathematics, Computer Science
- JACM
- 1991

A new string-matching algorithm is presented, which can be viewed as an intermediate between the classical algorithms of Knuth, Morris, and Pratt and Boyer and Moore, which presents the advantage of being remarkably simple which consequently makes its analysis possible. Expand

Discovering Repetitions in Strings

- Mathematics
- 1985

There are many variants of problems involving string matchings. The basic problem is to determine whether a pattern string x appears as a (contiguous) substring of a text y, i.e. whether for some… Expand

Patterns and Pattern-Matching in Trees: An Analysis

- Computer Science, Mathematics
- Inf. Control.
- 1983

It appears that for a wide class of statistics on trees, pattern-matching has a linear expected time complexity (in contrast to a quadratic worst-case behaviour). Expand

Fast searching in packed strings

- Computer Science, Mathematics
- J. Discrete Algorithms
- 2011

This paper studies the worst-case complexity of string matching on strings given in packed representation on the basis of classical Knuth-Morris-Pratt algorithm. Expand

#### References

SHOWING 1-5 OF 5 REFERENCES

STRING-MATCHING AND OTHER PRODUCTS

- Mathematics
- 1974

Abstract : The string-matching problem considered is to find all occurrences of a given pattern as a substring of another longer string. When the pattern is simply a given string of symbols, there is… Expand

Rapid identification of repeated patterns in strings, trees and arrays

- Computer Science, Mathematics
- STOC
- 1972

This paper describes a strategy for constructing efficient algorithms for solving two types of matching problems and develops explicit algorithms for these two problems applied to strings and arrays. Expand

The file transmission problem

- Computer Science
- AFIPS National Computer Conference
- 1973

An optimal derivation of A is a minimum-cost sequence of characters and copy commands which allow the receiving computer to construct the file A, and this algorithm is itself optimal in that both its run time and storage requirements are linear functions of the lengths of A and B. Expand

The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition

- Computer Science
- 1968

A container closure assembly for maintaining a sterile sealed container is provided having a ferrule having a top annular portion and a depending skirt portion for securing a resilient stopper for… Expand

Linear Time Simulation of Deterministic Two-Way Pushdown Automata

- Computer Science
- IFIP Congress
- 1971