Construction d'une arborescence de suffixes pour un algorithme de correspondance de chaînes dans une grande base de données

Question

J'ai eu une entrevue de stage la semaine dernière et on m'a posé une question concernant la recherche d'une chaîne particulière dans une grande base de données. Pendant l'interview, je n'en avais aucune idée, bien que je lui ai répondu "le hachage à plusieurs niveaux" car c'était le seul hin que je connaissais qui avait le meilleur temps. Après un peu de googling, je pense que la réponse qu'il attendait était arbre de suffixe. Maintenant, pendant ma recherche, j'ai trouvé mes algorithmes pour construire des arbres de suffixes et il y avait même des documents de recherche sur la façon de construire un arbre de suffixes !! Est-il vraiment possible d'implémenter l'arbre des suffixes pour l'algorithme de mise en correspondance des chaînes, en particulier pendant l'interview?

Ce serait génial si quelqu'un pouvait l'éclairer.

Merci à l'avance

Answer 1

Habituellement, l'intervieweur ne nécessitent pas de réponse précise pour ce genre de questions, ils sont plus intéressés par la façon dont vous pensez au sujet du problème et essayer de le résoudre. Bien sûr, mentionner les algorithmes connus pour résoudre le problème serait un plus, mais je trouve difficile de croire que quelqu'un aurait besoin de "suffixe arbre" comme réponse à cette question. Ceci étant dit, je ne considère pas que les algorithmes pour construire des arborescences de suffixes soient triviaux à implémenter.