Arbre des suffixes et Tries. Quelle est la différence ?

Question

Je suis en train de lire sur Tries communément appelés "arbres à préfixes" et Suffix Trees .
Bien que j'aie trouvé du code pour un Trie Je ne trouve pas d'exemple pour un Suffix Tree . De plus, j'ai l'impression que le code qui construit une Trie est le même que celui d'un Suffix Tree avec la seule différence que dans le premier cas, on stocke les préfixes et dans le second les suffixes.
C'est vrai ? Quelqu'un peut-il m'aider à éclaircir ce point dans ma tête ? Un exemple de code serait d'une grande aide !

Answer 1

Je vais vous donner des extraits pour vous permettre de mieux comprendre. Clause de non-responsabilité : je ne suis pas un expert et je connais ces DS grâce aux préparations d'entretiens de codage.

Tout d'abord, comme il a été dit plus haut : le suffixe trie est une structure composée de tables de hachage (variante la plus simple) où nous stockons toutes les variantes possibles. Ainsi, nous pouvons rechercher des sous-chaînes si nécessaire. Ex : 'abc'.

{'a': True, 
  'a': {'b': True},
  'a': {'b': {'c': True}}, 
  'b': True,
  'b': {'c': True},
  'c': True}

Et Trie, c'est quand on stocke des chaînes de caractères complètes pour vérifier si elles sont présentes. Ex : {'t': {'h': {'i': {'s': {'*': 'this'}}}}, 'y': {'o': {'*': 'yo'}}

Vous pouvez consulter la question pour plus d'explications sur Leetcode : Implement Trie (Prefix Tree). Lien : https://leetcode.com/problems/implement-trie-prefix-tree/