Par exemple, chaîne donnée « abc fghi bc kl abcd LKM abcdefg », la fonction doit retourner la chaîne « abcd » et le nombre de 2.Trouver la plus longue chaîne de répétition et le nombre de fois qu'il répète dans une chaîne
La solution AO (n^2) semble facile mais je cherche une meilleure solution.
Édité: Si rien de mieux que O (n^2) est possible, quelle approche serait la meilleure performance sage.
Vous pouvez résoudre ce dans le temps linéaire en construisant un suffix tree et prendre un chemin de la racine au plus profond interne nœud; cela vous donnera la plus longue chaîne répétée. Une fois que vous avez cette chaîne, il est trivial de compter le nombre de fois qu'il apparaît.
Une machine d'état pourrait probablement donner quelque chose de mieux que big-O (N^2).
EDIT: L'arbre suffixe suggéré dans l'autre réponse est une telle mise en œuvre d'une machine d'état :)
Votre nom d'utilisateur SO est un peu un don. –
c'est intentionnel pour parer le SNOBS. –
Problème de sous-chaîne répété le plus long: http://en.wikipedia.org/wiki/Longest_repeated_substring_problem – sambowry