1 | /* This file is part of Strigi Desktop Search |
2 | * |
3 | * Copyright (C) 2006 Jos van den Oever <jos@vandenoever.info> |
4 | * |
5 | * This library is free software; you can redistribute it and/or |
6 | * modify it under the terms of the GNU Library General Public |
7 | * License as published by the Free Software Foundation; either |
8 | * version 2 of the License, or (at your option) any later version. |
9 | * |
10 | * This library is distributed in the hope that it will be useful, |
11 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | * Library General Public License for more details. |
14 | * |
15 | * You should have received a copy of the GNU Library General Public License |
16 | * along with this library; see the file COPYING.LIB. If not, write to |
17 | * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
18 | * Boston, MA 02110-1301, USA. |
19 | */ |
20 | #ifndef STRIGI_KMPSEARCHER_H |
21 | #define STRIGI_KMPSEARCHER_H |
22 | |
23 | #include <string> |
24 | #include <stdlib.h> |
25 | |
26 | #include <strigi/strigiconfig.h> |
27 | |
28 | namespace Strigi { |
29 | /** |
30 | * Class for string search that uses the Knuth-Morris-Pratt algorithm. |
31 | * Code based on the example on |
32 | * http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm |
33 | **/ |
34 | class STREAMS_EXPORT KmpSearcher { |
35 | private: |
36 | std::string m_query; |
37 | int32_t* table; |
38 | int32_t len; |
39 | int32_t maxlen; |
40 | public: |
41 | KmpSearcher() :table(0) { } |
42 | KmpSearcher(const std::string& query); |
43 | ~KmpSearcher() { |
44 | if (table) { |
45 | free(table); |
46 | } |
47 | } |
48 | void setQuery(const std::string& query); |
49 | int32_t queryLength() const { return len; } |
50 | std::string query() const { return m_query; } |
51 | /** |
52 | * @brief Find the needle in @p haystack. |
53 | * @param haystack the text to search in. |
54 | * @param haylen the length of the text to search in. |
55 | * @return a pointer to the start of the match if a match is found |
56 | * Otherwise @c 0. |
57 | **/ |
58 | const char* search(const char* haystack, int32_t haylen) const; |
59 | }; |
60 | |
61 | } // end namespace Strigi |
62 | |
63 | #endif |
64 | |