/usr/share/doc/libghc-stringsearch-doc/html/Data-ByteString-Search-KMP.html

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Data.ByteString.Search.KMP</title><link href="ocean.css" rel="stylesheet" type="text/css" title="Ocean" /><script src="haddock-util.js" type="text/javascript"></script><script type="text/javascript">//<![CDATA[
window.onload = function () {pageLoad();setSynopsis("mini_Data-ByteString-Search-KMP.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-ByteString-Search-KMP.html">Source</a></li><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">stringsearch-0.3.6.6: Fast searching, splitting and replacing of ByteStrings</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Copyright</th><td>Justin Bailey
                  Chris Kuklewicz
                  Daniel Fischer</td></tr><tr><th>License</th><td>BSD3</td></tr><tr><th>Maintainer</th><td>Daniel Fischer &lt;daniel.is.fischer@googlemail.com&gt;</td></tr><tr><th>Stability</th><td>Provisional</td></tr><tr><th>Portability</th><td>non-portable (BangPatterns)</td></tr><tr><th>Safe Haskell</th><td>None</td></tr><tr><th>Language</th><td>Haskell98</td></tr></table><p class="caption">Data.ByteString.Search.KMP</p></div><div id="table-of-contents"><p class="caption">Contents</p><ul><li><a href="#g:1">Overview</a><ul><li><a href="#g:2">Complexity and Performance</a></li><li><a href="#g:3">Partial application</a></li></ul></li><li><a href="#g:4">Functions</a></li></ul></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Fast search of strict <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/bytestring-0.10.6.0/Data-ByteString.html#t:ByteString">ByteString</a></code> values using the
 Knuth-Morris-Pratt algorithm.</p><p>A description of the algorithm can be found at
 <a href="http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm">http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm</a>.</p><p>Original authors: Justin Bailey (jgbailey at gmail.com) and
 Chris Kuklewicz (haskell at list.mightyreason.com).</p></div></div><div id="synopsis"><p id="control.syn" class="caption expander" onclick="toggleSection('syn')">Synopsis</p><ul id="section.syn" class="hide" onclick="toggleSection('syn')"><li class="src short"><a href="#v:indices">indices</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/bytestring-0.10.6.0/Data-ByteString.html#t:ByteString">ByteString</a> -&gt; <a href="file:///usr/share/doc/ghc-doc/html/libraries/bytestring-0.10.6.0/Data-ByteString.html#t:ByteString">ByteString</a> -&gt; [<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Int.html#t:Int">Int</a>]</li><li class="src short"><a href="#v:nonOverlappingIndices">nonOverlappingIndices</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/bytestring-0.10.6.0/Data-ByteString.html#t:ByteString">ByteString</a> -&gt; <a href="file:///usr/share/doc/ghc-doc/html/libraries/bytestring-0.10.6.0/Data-ByteString.html#t:ByteString">ByteString</a> -&gt; [<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Int.html#t:Int">Int</a>]</li></ul></div><div id="interface"><h1 id="g:1">Overview</h1><div class="doc"><p>This module provides two functions for finding the occurrences of a
 pattern in a target string using the Knuth-Morris-Pratt algorithm.
 It exists only for systematic reasons, the functions from
 <a href="Data-ByteString-Search.html">Data.ByteString.Search</a> are much faster, except for very short patterns,
 in which case <a href="Data-ByteString-Search-DFA.html">Data.ByteString.Search.DFA</a> provides better functions.</p></div><h2 id="g:2">Complexity and Performance</h2><div class="doc"><p>The preprocessing of the pattern is <em>O</em>(<code>patternLength</code>) in time and space.
 The time complexity of the searching phase is <em>O</em>(<code>targetLength</code>) for both
 functions.</p><p>In most cases, these functions are considerably slower than the
 Boyer-Moore variants, performance is close to that of those from
 <a href="Data-ByteString-Search-DFA.html">Data.ByteString.Search.DFA</a>.</p></div><h2 id="g:3">Partial application</h2><div class="doc"><p>Both functions can be usefully partially applied. Given only a
 pattern, the auxiliary data will be computed only once, allowing for
 efficient re-use.</p></div><h1 id="g:4">Functions</h1><div class="top"><p class="src"><a name="v:indices" class="def">indices</a> <a href="src/Data-ByteString-Search-KMP.html#indices" class="link">Source</a></p><div class="subs arguments"><p class="caption">Arguments</p><table><tr><td class="src">:: <a href="file:///usr/share/doc/ghc-doc/html/libraries/bytestring-0.10.6.0/Data-ByteString.html#t:ByteString">ByteString</a></td><td class="doc"><p>Pattern to find</p></td></tr><tr><td class="src">-&gt; <a href="file:///usr/share/doc/ghc-doc/html/libraries/bytestring-0.10.6.0/Data-ByteString.html#t:ByteString">ByteString</a></td><td class="doc"><p>String to search</p></td></tr><tr><td class="src">-&gt; [<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Int.html#t:Int">Int</a>]</td><td class="doc"><p>Offsets of matches</p></td></tr></table></div><div class="doc"><p><code><code><a href="Data-ByteString-Search-KMP.html#v:indices">indices</a></code></code> finds the starting indices of all possibly overlapping
   occurrences of the pattern in the target string.
   If the pattern is empty, the result is <code>[0 .. <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Foldable.html#v:length">length</a></code> target]</code>.</p></div></div><div class="top"><p class="src"><a name="v:nonOverlappingIndices" class="def">nonOverlappingIndices</a> <a href="src/Data-ByteString-Search-KMP.html#nonOverlappingIndices" class="link">Source</a></p><div class="subs arguments"><p class="caption">Arguments</p><table><tr><td class="src">:: <a href="file:///usr/share/doc/ghc-doc/html/libraries/bytestring-0.10.6.0/Data-ByteString.html#t:ByteString">ByteString</a></td><td class="doc"><p>Pattern to find</p></td></tr><tr><td class="src">-&gt; <a href="file:///usr/share/doc/ghc-doc/html/libraries/bytestring-0.10.6.0/Data-ByteString.html#t:ByteString">ByteString</a></td><td class="doc"><p>String to search</p></td></tr><tr><td class="src">-&gt; [<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Int.html#t:Int">Int</a>]</td><td class="doc"><p>Offsets of matches</p></td></tr></table></div><div class="doc"><p><code><code><a href="Data-ByteString-Search-KMP.html#v:nonOverlappingIndices">nonOverlappingIndices</a></code></code> finds the starting indices of all
   non-overlapping occurrences of the pattern in the target string.
   It is more efficient than removing indices from the list produced
   by <code><a href="Data-ByteString-Search-KMP.html#v:indices">indices</a></code>.</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.16.1</p></div></body></html>
libghc-stringsearch-doc 0.3.6.6-4 / usr / share / doc / libghc-stringsearch-doc / html / Data-ByteString-Search-KMP.html
