9

For the two string searching algorithms: KMP and suffix tree, which is preferred in which cases? Give some practical examples.

Improve this question
5
  • 1
    What do you think yourself? It now just looks like you copied a part of your homework assignment. Commented Apr 10, 2010 at 11:22
  • This is no homework. I am a professional programmer working in a company. This question is just for gaining knowledge. Commented Apr 10, 2010 at 11:33
  • If you know the algorithms and know how they work, it should be not too hard to build up examples where the specific algorithm takes quite a large amount of steps and other examples where it is quite fast... (I think I remember building an example string consitsing just of 0 and 1, where KMP needed all the steps to be successful.) Commented Apr 10, 2010 at 11:43
  • @avd, if this isn't homework, you've phrased the question a bit awkward. Commented Apr 10, 2010 at 11:46
  • 2
    Very funny, avd. You are an intern who will only graduate in june. Commented Apr 10, 2010 at 15:39

1 Answer 1

Reset to default
11

A suffix tree is better if you will have to answer a lot of queries such as "is the needle present in the haystack?". KMP is better if you only have to search for one string in another single string, and not have to do it a lot of times.

A suffix tree is a much more general data structure, so you can do a lot more with it. See what you can do with it here. KMP is useful for finding if a string is a substring in another string.

You might also want to check out other algorithms, such as Boyer-Moore, Rabin-Karp and even the naive algorithm, as there are situations (inputs) in which one is better than the others.

Bottom line is:

  1. If you have a lot of queries like the one I mentioned above, it's worth to build a suffix tree and then answer each query faster.
  2. If you need to do more than those kinds of queries, a suffix tree is also worth building.
  3. If you only care about occasionally finding if a string is a substring of another string, then use KMP.
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.