scire
Sadh's C++ Impromptu Routines Ensemble
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
scire::StringMatchKMP< CharType, SzType > Class Template Reference

The Knuth-Morris-Pratt (KMP) algorithm for string-matching problem. More...

#include <knuth_morris_pratt.hpp>

Public Member Functions

 StringMatchKMP (const CharType *pattern, SzType length)
 Construct KMP pattern matching object with pattern to find. More...
 
bool ReadNext (CharType c)
 read next character in text stream More...
 

Static Public Member Functions

static SzType Position (const CharType *text, SzType textlen, const CharType *pattern, SzType patternlen)
 Find the position of the first occurrence of a substring in a text. More...
 

Detailed Description

template<typename CharType = char, typename SzType = size_t>
class scire::StringMatchKMP< CharType, SzType >

The Knuth-Morris-Pratt (KMP) algorithm for string-matching problem.

A KMP object is initialized with a pattern to find. Each character of text is then fed to the object with ReadNext() for matching.

ref:

  1. "Introduction to String Searching Algorithms - Rabin-Karp and Knuth-Morris-Pratt Algorithms". TheLlama (TopCoder Member)
  2. "<a href='http://www.ics.uci.edu/~eppstein/161/kmp/'>Example code for Knuth-Morris-Pratt algorithm</a>". Prof. David Eppstein, UC Irvine
  3. Knuth, Donald; Morris, James H., jr; Pratt, Vaughan (1977). "Fast pattern matching in strings". SIAM Journal on Computing 6 (2): 323-350. doi:10.1137/0206024. Zbl 0372.68005.

Definition at line 49 of file knuth_morris_pratt.hpp.

Constructor & Destructor Documentation

template<typename CharType = char, typename SzType = size_t>
scire::StringMatchKMP< CharType, SzType >::StringMatchKMP ( const CharType *  pattern,
SzType  length 
)
inline

Construct KMP pattern matching object with pattern to find.

Parameters
patternpatther to match
lengthlenght of pattern

Definition at line 131 of file knuth_morris_pratt.hpp.

Member Function Documentation

template<typename CharType = char, typename SzType = size_t>
static SzType scire::StringMatchKMP< CharType, SzType >::Position ( const CharType *  text,
SzType  textlen,
const CharType *  pattern,
SzType  patternlen 
)
inlinestatic

Find the position of the first occurrence of a substring in a text.

Returns
index (position) of text where substring (pattern) matched. if not found then the last index of text (text len)
Parameters
texttext to search in (haystack)
textlenlenth of text
patternpattern to find (substring, needle)
patternlenlength of pattern

Definition at line 170 of file knuth_morris_pratt.hpp.

template<typename CharType = char, typename SzType = size_t>
bool scire::StringMatchKMP< CharType, SzType >::ReadNext ( CharType  c)
inline

read next character in text stream

Returns
true if pattern matched
Parameters
cnext char in text stream

Definition at line 147 of file knuth_morris_pratt.hpp.


The documentation for this class was generated from the following file: