Table of Contents
49 relations: Aho–Corasick algorithm, Algorithm, Alphabet (formal languages), Approximate string matching, Array (data structure), Big O notation, Bioinformatics, Bitap algorithm, Boyer–Moore string-search algorithm, C standard library, Charles E. Leiserson, Clifford Stein, Commentz-Walter algorithm, Compressed pattern matching, Computer science, Depth-first search, Deterministic finite automaton, Diacritic, Finite set, Full-text search, Glibc, Graph matching, International Colloquium on Automata, Languages and Programming, Introduction to Algorithms, Knuth–Morris–Pratt algorithm, Lecture Notes in Computer Science, Ligature (writing), Markup language, Matching wildcards, Musl, Non-coding DNA, Pattern matching, Powerset construction, Rabin–Karp algorithm, Regular expression, Regular grammar, Regular language, Ron Rivest, Sequence alignment, String (computer science), Substring index, Suffix array, Suffix automaton, Suffix tree, Thomas H. Cormen, Trigram search, Two-way string-matching algorithm, Variable-width encoding, Vowel pointing.
- String matching algorithms
Aho–Corasick algorithm
In computer science, the Aho–Corasick algorithm is a string-searching algorithm invented by Alfred V. Aho and Margaret J. Corasick in 1975. String-searching algorithm and Aho–Corasick algorithm are string matching algorithms.
See String-searching algorithm and Aho–Corasick algorithm
Algorithm
In mathematics and computer science, an algorithm is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation.
See String-searching algorithm and Algorithm
Alphabet (formal languages)
In formal language theory, an alphabet, sometimes called a vocabulary, is a non-empty set of indivisible symbols/characters/glyphs, typically thought of as representing letters, characters, digits, phonemes, or even words.
See String-searching algorithm and Alphabet (formal languages)
Approximate string matching
In computer science, approximate string matching (often colloquially referred to as fuzzy string searching) is the technique of finding strings that match a pattern approximately (rather than exactly). String-searching algorithm and approximate string matching are string matching algorithms.
See String-searching algorithm and Approximate string matching
Array (data structure)
In computer science, an array is a data structure consisting of a collection of elements (values or variables), of same memory size, each identified by at least one array index or key.
See String-searching algorithm and Array (data structure)
Big O notation
Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.
See String-searching algorithm and Big O notation
Bioinformatics
Bioinformatics is an interdisciplinary field of science that develops methods and software tools for understanding biological data, especially when the data sets are large and complex.
See String-searching algorithm and Bioinformatics
Bitap algorithm
The bitap algorithm (also known as the shift-or, shift-and or Baeza-Yates-Gonnet algorithm) is an approximate string matching algorithm. String-searching algorithm and bitap algorithm are string matching algorithms.
See String-searching algorithm and Bitap algorithm
Boyer–Moore string-search algorithm
In computer science, the Boyer–Moore string-search algorithm is an efficient string-searching algorithm that is the standard benchmark for practical string-search literature. String-searching algorithm and Boyer–Moore string-search algorithm are string matching algorithms.
See String-searching algorithm and Boyer–Moore string-search algorithm
C standard library
The C standard library or libc is the standard library for the C programming language, as specified in the ISO C standard.
See String-searching algorithm and C standard library
Charles E. Leiserson
Charles Eric Leiserson (born 1953) is a computer scientist and professor at Massachusetts Institute of Technology (M.I.T.). He specializes in the theory of parallel computing and distributed computing.
See String-searching algorithm and Charles E. Leiserson
Clifford Stein
Clifford Seth Stein (born December 14, 1965), a computer scientist, is a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Science.
See String-searching algorithm and Clifford Stein
Commentz-Walter algorithm
In computer science, the Commentz-Walter algorithm is a string searching algorithm invented by Beate Commentz-Walter. String-searching algorithm and Commentz-Walter algorithm are string matching algorithms.
See String-searching algorithm and Commentz-Walter algorithm
Compressed pattern matching
In computer science, compressed pattern matching (abbreviated as CPM) is the process of searching for patterns in compressed data with little or no decompression.
See String-searching algorithm and Compressed pattern matching
Computer science
Computer science is the study of computation, information, and automation.
See String-searching algorithm and Computer science
Depth-first search
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.
See String-searching algorithm and Depth-first search
Deterministic finite automaton
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string.
See String-searching algorithm and Deterministic finite automaton
Diacritic
A diacritic (also diacritical mark, diacritical point, diacritical sign, or accent) is a glyph added to a letter or to a basic glyph.
See String-searching algorithm and Diacritic
Finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements.
See String-searching algorithm and Finite set
Full-text search
In text retrieval, full-text search refers to techniques for searching a single computer-stored document or a collection in a full-text database.
See String-searching algorithm and Full-text search
Glibc
The GNU C Library, commonly known as glibc, is the GNU Project implementation of the C standard library.
See String-searching algorithm and Glibc
Graph matching
Graph matching is the problem of finding a similarity between graphs.
See String-searching algorithm and Graph matching
International Colloquium on Automata, Languages and Programming
ICALP, the International Colloquium on Automata, Languages, and Programming is an academic conference organized annually by the European Association for Theoretical Computer Science and held in different locations around Europe.
See String-searching algorithm and International Colloquium on Automata, Languages and Programming
Introduction to Algorithms
Introduction to Algorithms is a book on computer programming by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
See String-searching algorithm and Introduction to Algorithms
Knuth–Morris–Pratt algorithm
In computer science, the Knuth–Morris–Pratt algorithm (or KMP algorithm) is a string-searching algorithm that 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. String-searching algorithm and Knuth–Morris–Pratt algorithm are string matching algorithms.
See String-searching algorithm and Knuth–Morris–Pratt algorithm
Lecture Notes in Computer Science
Lecture Notes in Computer Science is a series of computer science books published by Springer Science+Business Media since 1973.
See String-searching algorithm and Lecture Notes in Computer Science
Ligature (writing)
In writing and typography, a ligature occurs where two or more graphemes or letters are joined to form a single glyph.
See String-searching algorithm and Ligature (writing)
Markup language
A markup language is a text-encoding system which specifies the structure and formatting of a document and potentially the relationship between its parts.
See String-searching algorithm and Markup language
Matching wildcards
In computer science, an algorithm for matching wildcards (also known as globbing) is useful in comparing text strings that may contain wildcard syntax.
See String-searching algorithm and Matching wildcards
Musl
musl is a C standard library intended for operating systems based on the Linux kernel, released under the MIT License.
See String-searching algorithm and Musl
Non-coding DNA
Non-coding DNA (ncDNA) sequences are components of an organism's DNA that do not encode protein sequences.
See String-searching algorithm and Non-coding DNA
Pattern matching
In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern.
See String-searching algorithm and Pattern matching
Powerset construction
In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same formal language.
See String-searching algorithm and Powerset construction
Rabin–Karp algorithm
In computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm is a string-searching algorithm created by that uses hashing to find an exact match of a pattern string in a text. String-searching algorithm and Rabin–Karp algorithm are string matching algorithms.
See String-searching algorithm and Rabin–Karp algorithm
Regular expression
A regular expression (shortened as regex or regexp), sometimes referred to as rational expression, is a sequence of characters that specifies a match pattern in text.
See String-searching algorithm and Regular expression
Regular grammar
In theoretical computer science and formal language theory, a regular grammar is a grammar that is right-regular or left-regular.
See String-searching algorithm and Regular grammar
Regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to many modern regular expression engines, which are augmented with features that allow the recognition of non-regular languages).
See String-searching algorithm and Regular language
Ron Rivest
Ronald Linn Rivest (born May 6, 1947) is a cryptographer and computer scientist whose work has spanned the fields of algorithms and combinatorics, cryptography, machine learning, and election integrity.
See String-searching algorithm and Ron Rivest
Sequence alignment
In bioinformatics, a sequence alignment is a way of arranging the sequences of DNA, RNA, or protein to identify regions of similarity that may be a consequence of functional, structural, or evolutionary relationships between the sequences.
See String-searching algorithm and Sequence alignment
String (computer science)
In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.
See String-searching algorithm and String (computer science)
Substring index
In computer science, a substring index is a data structure which gives substring search in a text or text collection in sublinear time.
See String-searching algorithm and Substring index
Suffix array
In computer science, a suffix array is a sorted array of all suffixes of a string.
See String-searching algorithm and Suffix array
Suffix automaton
In computer science, a suffix automaton is an efficient data structure for representing the substring index of a given string which allows the storage, processing, and retrieval of compressed information about all its substrings.
See String-searching algorithm and Suffix automaton
Suffix tree
In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values.
See String-searching algorithm and Suffix tree
Thomas H. Cormen
Thomas H. Cormen is an American politician and retired academic.
See String-searching algorithm and Thomas H. Cormen
Trigram search
Trigram search is a method of searching for text when the exact syntax or spelling of the target object is not precisely known or when queries may be regular expressions. String-searching algorithm and Trigram search are string matching algorithms.
See String-searching algorithm and Trigram search
Two-way string-matching algorithm
In computer science, the two-way string-matching algorithm is a string-searching algorithm, discovered by Maxime Crochemore and Dominique Perrin in 1991. String-searching algorithm and two-way string-matching algorithm are string matching algorithms.
See String-searching algorithm and Two-way string-matching algorithm
Variable-width encoding
A variable-width encoding is a type of character encoding scheme in which codes of differing lengths are used to encode a character set (a repertoire of symbols) for representation, usually in a computer.
See String-searching algorithm and Variable-width encoding
Vowel pointing
Vowel pointing is the inserting of signs used to indicate vowels in certain alphabets.
See String-searching algorithm and Vowel pointing
See also
String matching algorithms
- Aho–Corasick algorithm
- Apostolico–Giancarlo algorithm
- Approximate string matching
- Bitap algorithm
- Boyer–Moore string-search algorithm
- Boyer–Moore–Horspool algorithm
- Commentz-Walter algorithm
- Knuth–Morris–Pratt algorithm
- Levenshtein automaton
- Rabin–Karp algorithm
- Raita algorithm
- Spaced seed
- String-searching algorithm
- Trigram search
- Two-way string-matching algorithm
- Zhu–Takaoka string matching algorithm
References
Also known as Deterministic finite automata string search, Exact string matching, Naive string search, Pattern matching in strings, Search string, String matching, String matching algorithm, String matching algorithms, String search, String search algorithm, String search algorithms, String searching, String searching algorithm, String searching algorithms, Substring search, Text match, Text search, Text searching.