Metraipolis › archive › dc_7fe4f6dbb7d6

Aho–Corasick algorithm — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T13:03:51.313Z
SHA-256 of the archived text
b740de960bf3c4e74afef5e2419f18819acf2967fa8d09627cb8afba78fc9aab
Stable URL of this page
https://metraipolis.com/documento/dc_7fe4f6dbb7d6

How to cite

Aho–Corasick algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_7fe4f6dbb7d6 (Metraipolis archive dc_7fe4f6dbb7d6, sha256 b740de960bf3c4e74afef5e2419f18819acf2967fa8d09627cb8afba78fc9aab)
BibTeX
@misc{dc7fe4f6dbb7d6,
  title = {Aho–Corasick algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_7fe4f6dbb7d6; sha256 b740de960bf3c4e74afef5e2419f18819acf2967fa8d09627cb8afba78fc9aab},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In computer science, the Aho–Corasick algorithm is a string-searching algorithm invented by Alfred V. Aho and Margaret J. Corasick in 1975. It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all strings simultaneously. The complexity of the algorithm is linear in the length of the strings plus the length of the searched text plus the number of output matches. Because all matches are found, multiple matches will be returned for one string location if multiple strings from the dictionary match at that location (e.g. dictionary = a, aa, aaa, aaaa and input string is aaaa). Informally, the algorithm creates a trie using the strings in the dictionary and then constructs a finite-state machine from the trie by adding additional links between the nodes. These extra links allow fast transitions between failed string matches (e.g. a search for cart in a trie that does not contain cart, but contains art, and thus would fail at the node prefixed by car), to other branches of the trie that share a common suffix (e.g., in the previous case, a branch for attribute might be the best lateral transition). This allows the automaton to transition between string matches without the need for backtracking. When the string dictionary is known in advance (e.g. a computer virus database), the construction of the automaton can be performed once off-line and the compiled automaton stored for later use. In this case, its run time is linear in the length of the input plus the number of matched entries. The Aho—Corasick string-matching algorithm formed the basis of the original Unix command fgrep.

Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»).
Fonte: Wikipedia in inglese, voce «Aho–Corasick algorithm» — https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
Wikidata Q402342 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q402342
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1347628892, consultata il 2026-10-07T12:34:33.953Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: fe11a2ce4f88500880081e11ce28988a6b916bfff547e221bc315475d2b8d4e3