String-searching algorithm: Difference between revisions

Revision as of 11:08, 11 November 2015

Revision as of 22:58, 17 December 2015

Line 80:

===Stubs===

[[Knuth–Morris–Pratt algorithm|Knuth–Morris–Pratt]] computes a [[deterministic finite automaton|DFA]] that recognizes inputs with the string to search for as a suffix, [[Boyer–Moore string search algorithm|Boyer–Moore]] starts searching from the end of the needle, so it can usually jump ahead a whole needle-length at each step. Baeza–Yates keeps track of whether the previous ''j'' characters were a prefix of the search string, and is therefore adaptable to [[fuzzy string searching]]. The [[bitap algorithm]] is an application of Baeza–Yates' approach.

=== Index methods ===

Line 86:

=== Other variants ===

Some search methods, for instance [[trigram search]], are intended to find a "closeness" score between the search string and the text rather than a "match/non-match". These are sometimes called [[Approximate_string_matchingApproximate string matching|"fuzzy" searches]].

==See also==

Line 96:

<references />

*R. S. Boyer and J. S. Moore, ''[http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf A fast string searching algorithm],'' Carom. ACM 20, (10), 262–272(1977).

* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 32: String Matching, pp.&nbsp;906–932.

==External links==