blob: f62f53f4e4715b74495877645d96b93501c98910 (
plain)
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
|
/*
* suffix_tree.h
*
* Created on: May 17, 2010
* Author: Vlad
NOTE (graehl): this seems to be a (forward) trie of the suffixes (of sentences).
so O(m*n^2) for m sentences of length n.
For a real suffix tree (linear size/time), see:
http://en.wikipedia.org/wiki/Suffix_tree
http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
*/
#ifndef SUFFIX_TREE_H_
#define SUFFIX_TREE_H_
#include <string>
#include <map>
#include <vector>
template <class T>
class Node {
public:
std::map<T, Node> edge_list_;
int InsertPath(const std::vector<T>& p, int start, int end);
const Node* Extend(const T& e) const {
typename std::map<T, Node>::const_iterator it = edge_list_.find(e);
if (it == edge_list_.end()) return NULL;
return &it->second;
}
};
bool DEBUG = false;
template <class T>
int Node<T>::InsertPath(const std::vector<T>& p, int start, int end){
Node* currNode = this;
for(int i=start;i<= end; i++ ) {
currNode = &(currNode->edge_list_)[p[i]];
}
return 1;
}
#endif /* SUFFIX_TRIE_H_ */
|
