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 | 043986db93d7f49ab1b1017a2322767d56384f7f (patch) | |
| tree | fb323e629a1dca5326d786aa355a6aec9e7f5220 | |
| parent | 16a1e08d79ebe4e10ead48affc4074e8fcbc1b96 (diff) | |
comment
git-svn-id: https://ws10smt.googlecode.com/svn/trunk@90 ec762483-ff6d-05da-a07a-a48fb63a330f
| -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_ |