From e1bdd3ea0c018fa5071346d389766bff87a02efb Mon Sep 17 00:00:00 2001
From: graehl <graehl@ec762483-ff6d-05da-a07a-a48fb63a330f>
Date: Thu, 1 Jul 2010 19:22:01 +0000
Subject: comment

git-svn-id: https://ws10smt.googlecode.com/svn/trunk@90 ec762483-ff6d-05da-a07a-a48fb63a330f
---
 extools/suffix_tree.h | 8 ++++++++
 1 file changed, 8 insertions(+)

(limited to 'extools/suffix_tree.h')

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_
-- 
cgit v1.2.3