Document Zbl 1130.68313

from until

add line

Document Type:

Journal Articles

Collection Articles

Books

arXiv Preprints

Document Type:

Journal Articles

Collection Articles

Books

arXiv Preprints

Reset all

Natural-Language Search^EXPERIMENTAL

Help

Examples

Geometry Search for the term Geometry in any field. Queries are case-independent.

Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.

"Topological group" Phrases (multi-words) should be set in "straight quotation marks".

au:Bourbaki & ti:Algebra Search for author Bourbaki and title Algebra. The and-operator & is default and can be omitted.

Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.

Quasi* map* py:1989 The resulting documents have publication year 1989.

so:Eur* J* Mat* Soc* cc:14 Search for publications in a particular source with a Mathematics Subject Classification code in 14.

cc:*35 ! any:elliptic Search for documents about PDEs (prefix with * to search only primary MSC); the not-operator ! eliminates all results containing the word elliptic.

dt:b & au:Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.

py:2000-2015 cc:(94A | 11T) Number ranges when searching for publication year are accepted. Terms can be grouped within ( parentheses ).

la:chinese Find documents in a given language. ISO 639-1 (opens in new tab) language codes can also be used.

st:c r o Find documents that are cited, have references and have an open version.

Fields

ab Text from the summary or review

an zbMATH Open document ID (preliminary ID, Zbl number, JFM number, or ERAM number)

any Includes ab, au, cc, en, rv, so, ti, ut

arxiv arXiv preprint number

au Name of author, editor, or other contributor

br Name of a person with biographic references (to find documents about the life or work)

cc Code from the Mathematics Subject Classification (prefix with * to restrict to primary MSC)

ci zbMATH Open ID of a document cited in summary or review

db Database: documents in Zentralblatt für Mathematik/zbMATH Open (db:Zbl), Jahrbuch über die Fortschritte der Mathematik (db:JFM), Crelle's Journal (db:eram), arXiv (db:arxiv)

dt Type of the document: journal article (dt:j), collection article (dt:a), book (dt:b), preprint (dt:p)

doi Digital Object Identifier (DOI)

ed Name of the editor of a book or special issue

en External document ID: DOI, arXiv ID, ISBN, and others

la Language (use name, e.g., la:French, or ISO 639-1, e.g., la:FR)

li External link (URL)

na Number of authors (interval search with “-”)

pt Reviewing state: Reviewed (pt:r), Title Only (pt:t), Pending (pt:p), Scanned Review (pt:s), Not Reviewd (pt:n)

pu Name of publisher

py Year of publication (interval search with “-”)

rft Publications containing the given text in its list of references

rn ID of the reviewer

rv Name or ID of the reviewer

se ID of the serial

si swMATH ID of software referred to in a document

so Bibliographical source (serial title, volume/issue number, page range, year of publication, ISBN, etc.)

st State: is cited (st:c), has references (st:r), has open version (st:o)

sw Name of software referred to in a document

ti Title of the document

ut Keywords

Operators

a & b Logical and (default)

a | b Logical or

!ab Logical not

abc* Right wildcard

ab c Phrase

(ab c) Term grouping

Construction of Aho Corasick automaton in linear time for integer alphabets. (English) Zbl 1130.68313

Apostolico, Alberto (ed.) et al., Combinatorial pattern matching. 16th annual symposium, CPM 2005, Jeju Island, Korea, June 19–22, 2005. Proceedings. Berlin: Springer (ISBN 3-540-26201-6/pbk). Lecture Notes in Computer Science 3537, 168-177 (2005).

Summary: We present a new simple algorithm that constructs an Aho Corasick automaton for a set of patterns, \(P\), of total length \(n\), in \(O (n)\) time and space for integer alphabets. Processing a text of size \(m\) over an alphabet \(\Sigma\) with the automaton costs \(O(m\log \left|\Sigma\right| + k)\), where there are \(k\) occurrences of patterns in the text.
For the entire collection see [Zbl 1076.68002].

Cited in 2 Documents

MSC:

68R15	Combinatorics on words
68P05	Data structures
68Q45	Formal languages and automata

Cite Review PDF

Full Text: DOI