strigi-analyzer/ctg/kmpsearcher.h

   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