Stack Overflow
Stack Overflow

Questions tagged [suffix-tree]

A suffix tree is a data structure that stores all suffixes of a string. It is the basis for many fast algorithms on strings.

228 questions
1222
votes
7 answers

Ukkonen's suffix tree algorithm in plain English

I feel a bit thick at this point. I've spent days trying to fully wrap my head around suffix tree construction, but because I don't have a mathematical background, many of the explanations elude me as they start to make excessive use of mathematical…
Nathan Ridley
  • 33,766
  • 35
  • 123
  • 197
93
votes
7 answers

Suffix tree and Tries. What is the difference?

I am reading about Tries commonly known as Prefix trees and Suffix Trees. Although I have found code for a Trie I can not find an example for a Suffix Tree. Also I get the feeling that the code that builds a Trie is the same as the one for a Suffix…
Cratylus
  • 52,998
  • 69
  • 209
  • 339
58
votes
11 answers

How to call module written with argparse in iPython notebook

I am trying to pass BioPython sequences to Ilya Stepanov's implementation of Ukkonen's suffix tree algorithm in iPython's notebook environment. I am stumbling on the argparse component. I have never had to deal directly with argparse before. How…
Niels
  • 1,513
  • 1
  • 14
  • 21
48
votes
5 answers

Longest palindrome in a string using suffix tree

I was trying to find the longest palindrome in a string. The brute force solution takes O(n^3) time. I read that there is a linear time algorithm for it using suffix trees. I am familiar with suffix trees and am comfortable building them. How do you…
shreyasva
  • 13,126
  • 25
  • 78
  • 101
36
votes
1 answer

How is it possible to build a suffix tree in linear time?

To build a suffix tree, in the worst case if all the letter of the string are different the complexity would be something like n + (n-1) + (n-2) ... 1 = n*(n+1)/2 which is O(n^2). However according to http://en.wikipedia.org/wiki/Suffix_tree…
shreyasva
  • 13,126
  • 25
  • 78
  • 101
34
votes
5 answers

String analysis

Given a sequence of operations: a*b*a*b*a*a*b*a*b is there a way to get the optimal subdivision to enable reusage of substring. making a*b*a*b*a*a*b*a*b => c*a*c, where c = a*b*a*b and then seeing that a*b*a*b => d*d, where d = a*b all in…
Martin Kristiansen
  • 9,875
  • 10
  • 51
  • 83
28
votes
1 answer

How and when to create a suffix link in suffix tree?

Could anyone give me an example about how and when to create a suffix link in suffix tree? If my string is ABABABC, but do use a different example if that is better. Hope to give some pictures to illustrate every step. very appreciate.
lingguang1997
  • 451
  • 1
  • 4
  • 12
27
votes
1 answer

Understanding Ukkonen's algorithm for suffix trees

I'm doing some work with Ukkonen's algorithm for building suffix trees, but I'm not understanding some parts of the author's explanation for it's linear-time complexity. I have learned the algorithm and have coded it, but the paper which I'm using…
Vinicius Braz Pinto
  • 8,209
  • 3
  • 42
  • 60
23
votes
1 answer

How to generate suffix trees using a python library?

I need python library that can construct suffix trees and especially generalised suffix trees. Could you suggest me some libraries. Thanks.
ashim
  • 24,380
  • 29
  • 72
  • 96
20
votes
3 answers

really hard to understand suffix tree

I've been searching for tutorials about suffix tree for quite a while. In SO, I found 2 posts about understanding suffix tree: 1, 2. But I can't say that I understand how to build one, Oops. In Skiena's book Algorithm design manual, he says: Since…
Alcott
  • 17,905
  • 32
  • 116
  • 173
20
votes
3 answers

Strange algorithm performance

For context, I wrote this algorithm to get the number of unique substrings of any string. It builds the suffix tree for the string counting the nodes it contains and returns that as the answer. The problem I wanted to solve required a O(n) algorithm…
mjgalindo
  • 856
  • 11
  • 26
17
votes
2 answers

Suffix Arrays vs Suffix Trees

I just wanna know, when a suffix tree is superior to an enhanced suffix array. After reading Replacing suffix trees with enhanced suffix arrays i don't see a reason to use suffix trees anymore. Some methods can get complicated, but you can do…
Nicolas
  • 950
  • 1
  • 7
  • 15
16
votes
2 answers

Approximate substring matching using a Suffix Tree

This article discusses approximate substring matching techniques that utilize a suffix tree to improve matching time. Each answer addresses a different algorithm. Approximate substring matching attempts to find a substring (pattern) P in a string T…
Pooven
  • 1,744
  • 1
  • 25
  • 44
15
votes
5 answers

Generalized Suffix Tree Java Implementation

I am looking for a Java implementation of the Generalized Suffix Tree (GST) with the following features: After the creation of the GST from say 1000 strings I would like find out how many of these 1000 strings contains some other string 's'. The…
user119746
14
votes
3 answers

Looking for the suffix tree implementation in C#?

I've implemented a basic search for a research project. I'm trying to make the search more efficient by building a suffix tree. I'm interested in a C# implementation of the Ukkonen algorith. I don't want to waste time rolling my own if such…
Goran
  • 6,798
  • 9
  • 41
  • 57
1
2 3
…
15 16