2
Par exemple, dans « 12345123451234512345 », ce qui est un algorithme efficace pour trouver « 12345 »?Un algorithme et un code efficaces pour trouver le cycle dans une chaîne en C++?
codage en C++.
Merci.
A
Répondre
3
aller sur votre seul exemple:
12345123451234512345 retours 12345
Je pense que ce que vous voulez est de trouver la plus longue aiguille possible qui se répète pour compléter la botte de foin, à savoir 1212121212 =>12, 444 =>4 et ainsi de suite.
La solution la plus simple serait de choisir le premier caractère et courir à travers la chaîne pour comparer les matchs. Si, à un moment donné, vous rencontrez une discordance, choisissez les deux premiers caractères et parcourez toute la chaîne de caractères, et ainsi de suite, jusqu'à ce que la taille de votre fenêtre devienne supérieure à la moitié de la chaîne.
complexité doit être O (n^2)
Vous pouvez optimiser la taille dont la fenêtre vous décrochez basée sur la longueur de la chaîne, à savoir la taille de la fenêtre ne peut être la longueur de diviseurs de la chaîne.
+0
Si vous êtes après le plus long possible, la chaîne "1234512345" n'est-elle pas répétée deux fois dans l'exemple? – abelenky
+0
@abelenky: La fenêtre augmente de taille 1 partir, avec mon algorithme vous arrêter à 12345 car elle correspondra à la chaîne entière =) –
+0
pour 444 ne la réponse est 44? –
Questions connexes
- 1. comment trier un tableau en C dans un cycle?
- 2. Un ensemble trouver un algorithme
- 3. algorithme pour trouver un point zéro
- 4. Algorithme pour trouver un mot sur Boggle
- 5. Algorithme pour trouver un trou dans un graphe unidimensionnel infini
- 6. Des moyens efficaces pour trouver un élément dans un tableau Javascript
- 7. Trouver un algorithme RBTREE en O (logn)
- 8. Algorithme C# pour trouver différentes combinaisons possibles
- 9. Quel est le meilleur algorithme pour trouver un article connexe?
- 10. Trouver le bon/meilleure combinaison de piste pour une distance donnée, en utilisant un algorithme génétique
- 11. Qu'est-ce qu'un algorithme typique pour trouver une chaîne dans une chaîne?
- 12. Statistiques hebdomadaires efficaces pour un QuerySet
- 13. Algorithme pour trouver l'ensemble indépendant 'maximal' dans un graphe simple
- 14. en utilisant le code c pour trouver le ratio
- 15. Comment concevoir un algorithme pour trouver le plus grand nombre dans une liste de nombres?
- 16. Algorithme C# qui réorganise les caractères dans une chaîne
- 17. algorithme pour trouver des arêtes en utilisant des sommets (2D et 3D) dans un maillage
- 18. Existe-t-il un algorithme pour transformer un simple code Haxe en fichiers de code C/C++?
- 19. Algorithme pour trouver l'anagramme le plus long
- 20. algorithme pour trouver ajoutés/éléments supprimés dans un tableau
- 21. Trouver le caractère occupant un index particulier dans une chaîne
- 22. Algorithme pour trouver le nombre qui apparaît le plus dans une rangée - C++
- 23. Comment trouver une chaîne dans une chaîne et la remplacer?
- 24. trouver une chaîne dans un fichier gzippé dans un dossier
- 25. Comment trouver une chaîne dans un tableau en PHP?
- 26. Algorithme pour trouver une forme carrée dans une image?
- 27. Algorithme C# pour colorer un certain pourcentage
- 28. C - Comment créer un motif dans un segment de code pour le reconnaître en mémoire?
- 29. Comment trouver un nombre dans une chaîne en utilisant JavaScript?
- 30. Regex pour trouver un nombre dans une chaîne
Est-ce devoir? Si c'est le cas, il serait poli de le dire. De plus, les questions «envoyez-moi le codez» obtiennent rarement de bonnes réponses. Qu'avez-vous essayé? Quels problèmes avez-vous rencontrés? –
La question n'est pas assez précise sur ce qu'est un "cycle" et quand une chaîne doit en trouver une. – zwol
Est-ce seulement des chiffres? Avez-vous une idée de la taille du cycle? Ou combien de fois il cycles? – Falmarri