Follow

J’ai passé la journée à étudier et essayer de programmer l’algorithme d’Ukkonen pour construire un suffix tree. Au final mon programme fonctionne à 80 %, je pense que c’est un des algos les plus difficiles que j’ai eu à programmer jusqu’à présent.

Quoique ça soit de la mécanique assez fine, le résultat vaut le coup puisqu’on calcule le suffix tree en O(n) au lieu de O(n^2) en temps (et O(n) en espace).

La meilleure description que j’ai pu trouver est stackoverflow.com/questions/94.

Sign in to participate in the conversation
La Quadrature du Net - Mastodon - Media Fédéré

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!