00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
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 };
00066
00067 }
00068 }
00069
00070 #include <claw/impl/kmp.tpp>
00071
00072 #endif // __CLAW_KMP_HPP__