Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
* KnuthMorrisPratt.h
*
* Created on: 5. 11. 2014
* Author: Jan Travnicek
*/
#ifndef _ARBOLOGY_KNUTH_MORRIS_PRATT_H_
#define _ARBOLOGY_KNUTH_MORRIS_PRATT_H_
#include <set>
#include <common/multipleDispatch.hpp>
#include <tree/TreeFeatures.h>
namespace arbology {
namespace exact {
/**
* Implementation of BMH for MI(E+\eps)-EVY course 2014
* To get rid of zeros in BCS table we ignore last haystack character
*/
class KnuthMorrisPratt : public std::DoubleDispatch < std::set < unsigned >, tree::TreeBase, tree::TreeBase > {
public:
/**
* Search for pattern in linear string.
* @return set set of occurences
*/
static std::set < unsigned > match ( const tree::Tree & subject, const tree::Tree & pattern );
static std::set < unsigned > match ( const tree::PrefixRankedBarTree & subject, const tree::PrefixRankedBarTree & pattern );
static std::set < unsigned > match ( const tree::PrefixRankedBarTree & subject, const tree::PrefixRankedBarPattern & pattern );
static KnuthMorrisPratt & getInstance ( ) {
static KnuthMorrisPratt res;
return res;
}
};
} /* namespace exact */
} /* namespace arbology */
#endif /* _ARBOLOGY_KNUTH_MORRIS_PRATT_H_ */