CLAW Library (a C++ Library Absolutely Wonderful) 1.5.5
kmp.hpp
Go to the documentation of this file.
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-2010 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@yahoo.fr
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__