About: Knuth–Morris–Pratt algorithm

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Knuth–Morris–Pratt algorithm Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

In computer science, the Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

Attributes	Values
rdfs:label	Knuth–Morris–Pratt algorithm (en)
rdfs:comment	In computer science, the Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters. (en)
sameAs	Knuth–Morris–Pratt algorithm
dbp:wikiPageUsesTemplate	dbt:Citation_needed dbt:Cite_book dbt:Color dbt:Donald_Knuth_navbox dbt:Reflist dbt:Short_description dbt:Wikibooks dbt:Infobox_algorithm dbt:Strings
Subject	1970 in computing Articles with example pseudocode Donald Knuth String matching algorithms
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm?oldid=1064080627&ns=0
Wikipage page ID	253227 (xsd:integer)
page length (characters) of wiki page	33699 (xsd:nonNegativeInteger)
Wikipage revision ID	1064080627 (xsd:integer)
Link from a Wikipage to another Wikipage	Algorithm Automata theory Big O notation Brute-force search 1970 in computing Articles with example pseudocode Donald Knuth String matching algorithms James H. Morris David Eppstein Donald Knuth Pseudocode Time complexity Algorithmic complexity Computer science Vaughan Pratt String-searching algorithm String (computer science) Substring Yuri Matiyasevich Lexicographically minimal string rotation Real-time computing
has abstract	In computer science, the Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters. The algorithm was conceived by James H. Morris and independently discovered by Donald Knuth "a few weeks later" from automata theory.Morris and Vaughan Pratt published a technical report in 1970.The three also published the algorithm jointly in 1977. Independently, in 1969, Matiyasevich discovered a similar algorithm, coded by a two-dimensional Turing machine, while studying a string-pattern-matching recognition problem over a binary alphabet. This was the first linear-time algorithm for string matching. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm
is Wikipage redirect of	Knuth-Morris-Pratt Knuth-Morris-Pratt Algorithm Knuth-Morris-Pratt string matching algorithm Knuth-Pratt-Morris Knuth-Pratt-Morris algorithm Knuth-morris-pratt Knuth-morris-pratt algorithm Knuth-pratt-morris algorithm Knuth Morris Pratt Knuth Morris Pratt algorithm Knuth morris pratt algorithm Knuth–Morris–Pratt Knuth-Morris-Pratt algorithm Failure function KMP algorithm KMP search Kmp search Nuth-Morris-Pratt string matching algorithm
is Link from a Wikipage to another Wikipage of	List of terms relating to algorithms and data structures Boyer–Moore–Horspool algorithm James H. Morris Donald Knuth Jewels of Stringology KMP List of eponyms (A–K) List of multiple discoveries List of algorithms Index of combinatorics articles Knuth-Morris-Pratt Knuth-Morris-Pratt Algorithm Knuth-Morris-Pratt string matching algorithm Knuth-Pratt-Morris Knuth-Pratt-Morris algorithm Knuth-morris-pratt Knuth-morris-pratt algorithm Knuth-pratt-morris algorithm Knuth Morris Pratt Knuth Morris Pratt algorithm Knuth morris pratt algorithm Knuth–Morris–Pratt Input enhancement (computer science) Knuth Knuth-Morris-Pratt algorithm Lexicographically minimal string rotation Failure function KMP algorithm KMP search Kmp search Nuth-Morris-Pratt string matching algorithm
is known for of	Vaughan Pratt
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (71 GB total memory, 2 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software