Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 1 down vote favorite

  1. Build a suffix tree from a string.

  2. While creating the suffix tree, count re-occurrences of every substring and save it on the number of occurrences on the node.

  3. Then do a BFS search on the tree (from shorter to longer strings) and find the substring with the highest count.

The time to construct suffix tree is O(n). BFS search find all the substring and return substring with highest count which required O(k), k is the number of substrings found from suffix tree. So the worst case complexity is O(n+k) or the complexity is O(nk)?

share|improve this question
2  
It this homework? – mouviciel Sep 14 '11 at 15:37

closed as not a real question by Konrad Rudolph, Robert Harvey, Mark Trapp Sep 15 '11 at 23:15

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, see the FAQ.

2 Answers

up vote 0 down vote

If you wan to have a better complexity, i think it's better to store the number of substring count in an array and return the highest count of the substring instead of using BFS...complexity is O(n)...

share|improve this answer
up vote 0 down vote

The highest occurring substring will obviously be a single letter ...therefore, you could simply count all the letters ...and this becomes O(text length) for constructing and O(alphabet size) to find out the highest occurring "substring". :)

If this is inaccurate, please edit your question and illustrate it with a small example the expected counts.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.