Implements "Knuth-Morris-Pratt" algorithm for searching a substring within a string.
While the well known "Boyer-Moore-Algorithm" is even faster in the average case, for uni-code characters its implementation would be efficient only with very long haystack strings.
For convenience, the following alias type names are available:
| TChar | The character type of the haystack and needle strings. |
| TSensitivity | The letter case sensitivity of the search.. |
Definition at line 25 of file search.inl.
Public Method Index: | |
| TStringSearch (const TString< TChar > &pNeedle=nullptr) | |
| ALIB_DLL | ~TStringSearch () |
| Destructor. | |
| ALIB_DLL void | Compile (const TString< TChar > &needle) |
| ALIB_DLL integer | Search (const TString< TChar > &haystack, integer startIdx=0) |
Protected Field Index: | |
| integer * | kmpTable = nullptr |
| The Knuth-Morris-Pratt prefix length table. | |
| integer | kmpTableLength = 0 |
| Length of kmpTable. | |
| TAString< TChar, lang::HeapAllocator > | needle |
| The needle set Knuth-Morris-Pratt prefix length table. | |
|
protected |
The Knuth-Morris-Pratt prefix length table.
Definition at line 32 of file search.inl.
|
protected |
Length of kmpTable.
Definition at line 35 of file search.inl.
|
protected |
The needle set Knuth-Morris-Pratt prefix length table.
Definition at line 29 of file search.inl.
|
inline |
Constructor. Passes the optional parameters to method Compile.
| pNeedle | The string to search. Defaults to NULL_STRING to allow parameterless construction with later invocation of Compile. |
Definition at line 45 of file search.inl.
| template ALIB_DLL alib::strings::util::TStringSearch< TChar, TSensitivity >::~TStringSearch | ( | ) |
Destructor.
Definition at line 28 of file search.cpp.
| template ALIB_DLL void alib::strings::util::TStringSearch< TChar, TSensitivity >::Compile | ( | const TString< TChar > & | needle | ) |
Resets this object to use the given string as the needle to search.
| needle | The needle to search. |
Definition at line 31 of file search.cpp.
| template ALIB_DLL integer alib::strings::util::TStringSearch< TChar, TSensitivity >::Search | ( | const TString< TChar > & | haystack, |
| integer | startIdx = 0 ) |
Searches for the needle in haystack starting at startIdx.
| haystack | The string to search in. |
| startIdx | The start of the search. Defaults to 0. |
-1 if not found. Definition at line 67 of file search.cpp.