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
28namespace 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 **/
34class STREAMS_EXPORT KmpSearcher {
35private:
36 std::string m_query;
37 int32_t* table;
38 int32_t len;
39 int32_t maxlen;
40public:
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