Est-il possible de trouver la plus longue sous-chaîne commune, la plus longue sous-chaîne palindromique, la plus longue sous-chaîne répétée, la recherche de tous les modèles et la sous-chaîne à l'aide de l'algorithme d'Ukkonen? Si oui, alors lequel dois-je utiliser puisque les deux algorithmes ont une complexité linéaire?Différence entre Knuth-Morris-Pratt (KMP) et l'arborescence de suffixes utilisant l'algorithme de Ukkonen pour la complexité temporelle.
Pour trouver la plus longue sous-chaîne commune, j'utiliserais l'algorithme de Kadane qui a une complexité linéaire. Pour la plus longue sous-chaîne palindromique, le choix serait l'algorithme de Manacher qui a également une complexité linéaire. Pour la chaîne répétée et la recherche de tous les modèles, oui le choix se résumerait entre KMP et Boyer-Moore. En ce qui concerne lequel, Boyer-Moore correspond au dernier caractère du modèle au lieu du premier avec l'hypothèse que s'il n'y a pas de match à la fin, pas besoin d'essayer de faire correspondre au début. KMP recherche les occurrences d'un mot W dans une chaîne de texte principale S en employant l'observation que lorsqu'une discordance se produit, en contournant ainsi le réexamen des caractères précédemment appariés. Cela rend KMP légèrement mieux optimisé pour les petits ensembles comme ACTGT.
Est-ce une question de devoirs? Et quelles recherches avez-vous faites jusqu'à présent? – AgataB
Non, ce n'est pas une question de devoirs. J'ai fait un peu de recherche à ce sujet. –