Search results

Create the page "Suffix tree" on this wiki! See also the search results found.

• Segment tree
  ...de and conquer|divide-and-conquer]] paradigm, which can be thought of as a tree of intervals of an underlying array, constructed so that queries on ranges ...e that we are doing so. Bear in mind, however, that other types of segment tree exist, which are discussed later in the article.
  21 KB (3,669 words) - 02:34, 6 April 2016
• Longest palindromic substring
  ...tandard data structures from the literature, the [[suffix tree]] and the [[suffix array]]. ===Suffix array===
  19 KB (3,066 words) - 10:05, 1 November 2016
• String
  ...when <math>s \sqsubset S</math> and <math>s \neq S</math>, with '''proper suffix''' defined analogously. ...od.uwaterloo.ca/~cs482/suffix-icalp03.pdf http://monod.uwaterloo.ca/~cs482/suffix-icalp03.pdf].</ref>:
  12 KB (1,959 words) - 23:56, 23 November 2011
• Tree
  ...e eponymous tall, woody plants, as these are also connected and acyclic (a tree is in one piece, but its branches never form cycles). A collection of disjo ...aph, any two of these three statements, taken together, imply the third ([[Tree/Proof of properties of trees|proof]]):
  17 KB (2,906 words) - 03:22, 12 December 2011
• Longest common substring
  The fastest solutions are obtained using suffix data structures. ===Suffix tree===
  7 KB (1,242 words) - 04:49, 29 May 2011
• Naive algorithm
  ...aystack rather than searched for in a linear fashion leads to the [[suffix tree]] data structure which reduces string search to mere traversal. All of thes
  2 KB (297 words) - 15:24, 29 June 2011
• String searching
  ...the trie corresponds, which is made possible by augmenting the trie with ''suffix links''. ==Suffix data structures==
  16 KB (2,766 words) - 19:54, 6 April 2011
• Preprocessing and postprocessing
  ...about how it matches shifts of itself. Likewise, constructing the [[suffix tree]] of a string is a form of preprocessing, which is very difficult to do eff
  4 KB (643 words) - 03:38, 21 November 2011
• Lowest common ancestor
  ...'''least common ancestor''' (LCA) of a nonempty set of nodes in a rooted [[tree]] is the unique node of greatest depth that is an ancestor of every node in ...thermore, the <math>\operatorname{LCA}(u,v)</math> is the only node in the tree for which this is true.
  11 KB (2,023 words) - 23:03, 5 April 2016
• Cartesian tree
  ...sian_tree.svg|250px|thumb|right|A sequence and its corresponding Cartesian tree]] ...[[inorder traversal]] is that sequence. This is known as the '''Cartesian tree''' for that sequence.
  17 KB (3,062 words) - 18:02, 13 June 2016
• Hidden constant factor
  ...the <math>O(\log n)</math> time associated with a [[balanced binary search tree]] operation. Thus, BBSTs implement a superset of the functionality of heaps ...of 2 for each additional dimension), and an <math>O(\log n)</math> segment tree operation is generally slower than an <math>O(\log n)</math> BIT operation,
  4 KB (675 words) - 08:49, 18 February 2012