diff options
| author | graehl <graehl@ec762483-ff6d-05da-a07a-a48fb63a330f> | 2010-07-01 19:22:01 +0000 |
|---|---|---|
| committer | graehl <graehl@ec762483-ff6d-05da-a07a-a48fb63a330f> | 2010-07-01 19:22:01 +0000 |
| commit | e1bdd3ea0c018fa5071346d389766bff87a02efb (patch) | |
| tree | d75472b09088130ba147410b9d3c78ddeeed2200 /extools/suffix_tree.h | |
| parent | af86feb1fbecbd9d25def761fcca89d2a0494de7 (diff) | |
comment
git-svn-id: https://ws10smt.googlecode.com/svn/trunk@90 ec762483-ff6d-05da-a07a-a48fb63a330f
Diffstat (limited to 'extools/suffix_tree.h')
| -rw-r--r-- | extools/suffix_tree.h | 8 |
1 files changed, 8 insertions, 0 deletions
diff --git a/extools/suffix_tree.h b/extools/suffix_tree.h index d3a9c08e..f62f53f4 100644 --- a/extools/suffix_tree.h +++ b/extools/suffix_tree.h @@ -3,6 +3,14 @@ * * 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_ |