Knuth–Morris–Pratt algorithm

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. ^[1]

13 relations: Algorithm, Big O notation, Computational complexity theory, Computer science, David Eppstein, Donald Knuth, James H. Morris, Lexicographically minimal string rotation, Pseudocode, Real-time computing, String-searching algorithm, Vaughan Pratt, Yuri Matiyasevich.

Algorithm

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

New!!: Knuth–Morris–Pratt algorithm and Algorithm · See more »

Big O notation

Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.

New!!: Knuth–Morris–Pratt algorithm and Big O notation · See more »

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

New!!: Knuth–Morris–Pratt algorithm and Computational complexity theory · See more »

Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

New!!: Knuth–Morris–Pratt algorithm and Computer science · See more »

David Eppstein

David Arthur Eppstein (born 1963) is an American computer scientist and mathematician.

New!!: Knuth–Morris–Pratt algorithm and David Eppstein · See more »

Donald Knuth

Donald Ervin Knuth (born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University.

New!!: Knuth–Morris–Pratt algorithm and Donald Knuth · See more »

James H. Morris

James Hiram Morris (born 1941) is a professor of Computer Science.

New!!: Knuth–Morris–Pratt algorithm and James H. Morris · See more »

Lexicographically minimal string rotation

In computer science, the lexicographically minimal string rotation or lexicographically least circular substring is the problem of finding the rotation of a string possessing the lowest lexicographical order of all such rotations.

New!!: Knuth–Morris–Pratt algorithm and Lexicographically minimal string rotation · See more »

Pseudocode

Pseudocode is an informal high-level description of the operating principle of a computer program or other algorithm.

New!!: Knuth–Morris–Pratt algorithm and Pseudocode · See more »

Real-time computing

In computer science, real-time computing (RTC), or reactive computing describes hardware and software systems subject to a "real-time constraint", for example from event to system response.

New!!: Knuth–Morris–Pratt algorithm and Real-time computing · See more »

String-searching algorithm

In computer science, string-searching algorithms, sometimes called string-matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text.

New!!: Knuth–Morris–Pratt algorithm and String-searching algorithm · See more »

Vaughan Pratt

Vaughan Pratt (born on April 12, 1944) is a Professor Emeritus at Stanford University, who was an early pioneer in the field of computer science.

New!!: Knuth–Morris–Pratt algorithm and Vaughan Pratt · See more »

Yuri Matiyasevich

Yuri Vladimirovich Matiyasevich, (Ю́рий Влади́мирович Матиясе́вич; born March 2, 1947, in Leningrad) is a Russian mathematician and computer scientist.

New!!: Knuth–Morris–Pratt algorithm and Yuri Matiyasevich · See more »

Redirects here:

Failure function, KMP algorithm, KMP search, Kmp search, Knuth Morris Pratt, Knuth Morris Pratt algorithm, Knuth morris pratt algorithm, Knuth-Morris-Pratt, Knuth-Morris-Pratt Algorithm, 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, Nuth-Morris-Pratt string matching algorithm.

References

[1] https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm

Unionpedia is a concept map or semantic network organized like an encyclopedia – dictionary. It gives a brief definition of each concept and its relationships.

This is a giant online mental map that serves as a basis for concept diagrams. It's free to use and each article or document can be downloaded. It's a tool, resource or reference for study, research, education, learning or teaching, that can be used by teachers, educators, pupils or students; for the academic world: for school, primary, secondary, high school, middle, technical degree, college, university, undergraduate, master's or doctoral degrees; for papers, reports, projects, ideas, documentation, surveys, summaries, or thesis. Here is the definition, explanation, description, or the meaning of each significant on which you need information, and a list of their associated concepts as a glossary. Available in English, Spanish, Portuguese, Japanese, Chinese, French, German, Italian, Polish, Dutch, Russian, Arabic, Hindi, Swedish, Ukrainian, Hungarian, Catalan, Czech, Hebrew, Danish, Finnish, Indonesian, Norwegian, Romanian, Turkish, Vietnamese, Korean, Thai, Greek, Bulgarian, Croatian, Slovak, Lithuanian, Filipino, Latvian, Estonian and Slovenian. More languages soon.

All the information was extracted from Wikipedia, and it's available under the Creative Commons Attribution-ShareAlike License.

Unionpedia is not endorsed by or affiliated with the Wikimedia Foundation.

Google Play, Android and the Google Play logo are trademarks of Google Inc.