Claw 1.7.0
|
00001 /* 00002 CLAW - a C++ Library Absolutely Wonderful 00003 00004 CLAW is a free library without any particular aim but being useful to 00005 anyone. 00006 00007 Copyright (C) 2005-2011 Julien Jorge 00008 00009 This library is free software; you can redistribute it and/or 00010 modify it under the terms of the GNU Lesser General Public 00011 License as published by the Free Software Foundation; either 00012 version 2.1 of the License, or (at your option) any later version. 00013 00014 This library is distributed in the hope that it will be useful, 00015 but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00017 Lesser General Public License for more details. 00018 00019 You should have received a copy of the GNU Lesser General Public 00020 License along with this library; if not, write to the Free Software 00021 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00022 00023 contact: julien.jorge@gamned.org 00024 */ 00031 #ifndef __CLAW_KMP_HPP__ 00032 #define __CLAW_KMP_HPP__ 00033 00034 #include <map> 00035 00036 namespace claw 00037 { 00038 namespace text 00039 { 00044 template<class RandomIterator> class kmp 00045 { 00046 public: 00047 template <class UnaryPredicate> 00048 void operator()(const RandomIterator pattern_begin, 00049 const RandomIterator pattern_end, 00050 const RandomIterator text_begin, 00051 const RandomIterator text_end, 00052 UnaryPredicate& action) const; 00053 00054 private: 00055 unsigned int common_prefix_length( const RandomIterator begin_1, 00056 const RandomIterator begin_2, 00057 const RandomIterator end_1, 00058 const RandomIterator end_2 ) const; 00059 00060 void z_boxes(const RandomIterator begin, const RandomIterator end, 00061 std::map<unsigned int, unsigned int>& out) const; 00062 00063 void spi_prime(const RandomIterator begin, const RandomIterator end, 00064 std::map<unsigned int, unsigned int>& out) const; 00065 }; // class kmp 00066 00067 } // namespace text 00068 } // namespace claw 00069 00070 #include <claw/impl/kmp.tpp> 00071 00072 #endif // __CLAW_KMP_HPP__