Les meilleures sources algorithmes

Les meilleures sources algorithmesConsultez toutes les sources

Nombre d'auteurs : 1, nombre de sources : 15, dernière mise à jour : 4 janvier 2007

Sommaire→Algorithmes sur les chaînes de caractères

Recherche de sous-chaines par méthode naïve (bruteforce)

Version hors-ligne

Recherche de sous-chaines par méthode naïve (bruteforce)

Entrée:

Sélectionnez

C : Chaine dans laquelle on doit chercher la sous chaîne, indexé de 1 à n 
S : Chaine à chercher, indexée de 1 à m

Sortie:

Sélectionnez

VRAI si la chaine S existe dans C, 
FAUX sinon.

Pseudo-Code :

Sélectionnez

POUR i de 1 à n-m FAIRE 
    POUR j de 1 à m FAIRE 
	    SI S[i + j - 1] différent de C[j] ALORS 
		    PASSER au i suivant 
		FIN SI 
		SI j == m ALORS 
		    RENVOYER VRAI 
		FIN SI 
	FIN POUR 
FIN POUR 
RENVOYER FAUX

Complexité :

Sélectionnez

O(mn)

Créé le 17 décembre 2006 par Romuald Perrot

Version hors-ligne

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2006 Developpez Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.