Comment implémenter un algorithme pour résoudre ce devoirs suivants en temps O (n) par suffixe?

Question

J'ai une question en bioinformatique. Vous pouvez le résoudre par structure arborescente de suffixe. Etant donné une chaîne S = S [1 ... n] et un nombre k, nous voulons trouver la plus petite sous-chaîne de S qui se produit dans S exactement k fois, si elle existe. Comment résoudre ce problème en temps O (n)?

Answer 1

Construit l'arbre de suffixe de la chaîne O (N).

Compter pour chaque nœud le nombre de feuilles qu'il contient O (N).

Trouvez un nœud où le count == k. Le chemin de la racine à ce nœud est une sous-chaîne qui répète exactement k fois.