Building a suffix tree for a string matching algorithm in large database

I had an internship interview last 开发者_StackOverflowweek and I was given a question regarding searching for a particular string in a large database. I was totally clueless about it during the interview though I just gave a reply the"multi-level hashing" as that was the only hin I knew which had the best time efficiency, After a bit googling I think the answer he expected was that of suffix tree. Now during my search I found my algorithms for building suffix trees and there were even research papers on how to build suffix tree!! So is it really possible to implement the suffix tree for string matching algorithm especially during interview time?

It would be great if someone can throw light on it.

Thanks in advance

---

Usually the interviewer don't need a precise answer for these kind of questions, they're more interested in the way you think about the problem and try to solve it.

Of course, mentioning known algorithms to solve the problem would be a plus, but I find it hard to believe that someone would require "suffix tree" as an answer for that question.

That being said, I don't consider the algorithms to build suffix trees trivial to implement.