algo : trouver le nombre le 'pattern' le plus frequent

[b0fh]

Alors dans ton exemple premier, la plus longue chaine serait plutôt "aabcd" qui se répète deux fois.

Si tu considères que c'est correct, une implémentation O(n log n) en Haskell:

Code :

{-# LANGUAGE NoMonomorphismRestriction #-}
import Control.Applicative
import Data.List
import Data.Ord

commonPrefix = ((map fst . takeWhile (uncurry (==))) .) . zip
commons = (zipWith commonPrefix <*> tail) . sort . tails
best = maximumBy (comparing length) . commons

-- best "aaaabcdaadabddcbadcacddbaabbadaabcddcabcd" = "aabcd"

Explications: "tails" crée la liste de tous les suffixes (çad les n derniers caractères, pour n de 1 à la longueur de la chaine). En Haskell prendre la queue d'une liste ne cause pas de réallocation, en C tu pourrais faire pareil en remplissant simplement un tableau de pointeurs vers chaque début possible de la string.

Ce tableau est ensuite trié (tri externe veut dire qu'on trie des pointeurs vers des blogs de données potentiellement beaucoup plus gros, et qu'on évite le cout du déplacement ou du fetch complet desdonnées.)

Ton plus long préfixe répété sera donc forcément sur deux lignes contigues. On considère chaque couple de ligne contigues (le zipWith <*> tails) en y appliquant commonPrefix (qui cherche le plus long préfixe commun possible).

On prend les préfixes résultants, on les trie par longueur, et on prend le plus long.

Si tu veux un critère arbitraire sur la longueur et le nombre de répétitions, tu pourrais placer tous ces préfixes dans un Patricia Tree puis parcourir l'arbre en calculant une métrique quelconque sur chaque noeud.