编程知识 cdmana.com

Algorithme de modèle de correspondance KMP - - interprétation au niveau de la nounou (version graphique)

Table des matières

Un.,C'est écrit devant

2.,Algorithme simple de correspondance de motifs

Trois,KPMAlgorithme de correspondance de modèle pour

1,Principe de l'algorithme

2,NEXTDérivation du tableau

3,Réalisation de l'algorithme

4,Amélioration de l'algorithme

Quatre,Tous les codes

Cinq, Remarques finales


Un.,C'est écrit devant

Comprendre un algorithme optimisé et efficace,Est basé sur un algorithme commun amélioré et amélioré,Allez.KMPAvant l'algorithme,Nous devrions d'abord comprendre l'algorithme de modèle simple.

2.,Algorithme simple de correspondance de motifs

Trouver un mot dans un article( équivalent à une grande chaîne ) Problèmes de positionnement dans .L'opération de positionnement de ce substrat est souvent appelée appariement de motifs de la chaîne,Ça devrait être l'une des opérations les plus importantes de la chaîne.

Supposons que nous devions passer de la chaîne principale ci - dessous S="goodgoogle”Moyenne,TrouverT=“google" La position de ce substrat .Nous avons généralement besoin des étapes suivantes.

1.Chaîne principaleS Commencez en premier. ,SAvecTLes trois premières lettres correspondent,Mais...S La quatrième lettre est dEtTOui.g. La première correspondance a échoué .Comme le montre la figure,Où les lignes verticales représentent l'égalité,La ligne de flexion de la foudre indique une inégalité.

 2,Chaîne principaleS Deuxième position. ,Chaîne principaleS Les initiales sont: o, Pour correspondre T Les initiales sont: g,Échec de la correspondance,

3,Chaîne principaleS Troisième position. ,Chaîne principaleS Les initiales sont: o, Pour correspondre T Les initiales sont: g,Échec de la correspondance,

 4,Chaîne principaleS Quatrième position. ,Chaîne principaleS Les initiales sont: d, Pour correspondre T Les initiales sont: g,Échec de la correspondance,

5,Chaîne principaleS La cinquième place commence. ,SAvecT,6 Toutes les lettres correspondent ,Correspondance réussie,


 

En termes simples,C'est - à - dire que chaque caractère de la chaîne principale commence comme une sous - chaîne,Correspond à la chaîne à apparier. Faire un grand cycle sur la chaîne principale , Début de chaque caractère T Un petit cycle de la longueur ,Jusqu'à ce que la correspondance soit réussie ou que toutes les traversées soient terminées.

Nous avons déjà implémenté l'algorithme de correspondance de modèle avec d'autres opérations de la chaîne Index.Considérez maintenant d'autres opérations sans chaînes,Au lieu de cela, le même algorithme n'est implémenté qu'avec un tableau de base. Notez que nous supposons que la chaîne principale S Et le substrat à apparier T La longueur existe S[0]AvecT[0]Moyenne.Le Code d'implémentation est le suivant: 

/*  Renvoie le substrat TDans la chaîne principaleSMoyennepos Position après les caractères .S'il n'existe pas, La valeur de retour de la fonction est 0. */
/*  TNon vide,1≤pos≤StrLength(S). */
int Index_KMP(String S, String T, int pos) 
{
	int i = pos;		/* i Pour la chaîne principale S Indice de position actuel moyen ,SiposNon.1,Depos La position commence à correspondre  */
	int j = 1;			/* j Pour substrats T Indice de position actuel moyen  */
	int next[255];		/* Définition InextTableau */
	get_next(T, next);	/*  Paire de cordes T Analyse ,Je l'ai.nextTableau */
	while (i <= S[0] && j <= T[0]) /* SiiMoins deS Longueur et jMoins deT En longueur ,La boucle continue. */
	{
		if (j==0 || S[i] == T[j]) 	/*  Deux lettres égales continuent , Avec des algorithmes simples j=0Jugement */
      	{
         	++i;
         	++j; 
      	} 
      	else 			/* Le pointeur recule et recommence à correspondre */
      	 	j = next[j];/* j Retour à la bonne position ,iValeur constante */
	}
	if (j > T[0]) 
		return i-T[0];
	else 
		return 0;
}

Analyse, Quel est le meilleur scénario? ?C'est le succès de l'appariement dès le début,Par exemple,“googlegood” Allez - y. “googe”,La complexité temporelle est0[1). Un peu moins. ,Si, comme dans le deuxième exemple、Trois、 Quatre. ,Les initiales ne correspondent pas à chaque fois,Alors oui.TLe cycle de la chaîne n'a pas besoin d'être fait,Par exemple,“"abcdefgoogle” Allez - y. “google”.Donc la complexité temporelle est0(n+m),Parmi euxn Longueur de la chaîne principale ,mEst la longueur du substrat à correspondre. Selon le principe de probabilité égale ,En moyenne(n+m)/2Recherche secondaire,La complexité temporelle esto(n+m).
Quel est le pire scénario?C'est que chaque correspondance infructueuse se se produit dans la chaîneTDernier caractère de. Prenons un exemple très extrême. . La chaîne principale est S=“0o000000000000000000000000000000000000000000000001”, Et le substrat à apparier est T=“0000000001”, Le premier est 49- Oui.“0”Et1- Oui.“1” La chaîne principale de ,Ce dernier est9- Oui.“0”Et1- Oui.“1”Substrats de.Au moment de la correspondance, Chaque fois qu'il faut TLe caractère moyen tourne jusqu'au dernier chiffre pour trouver:Oh, mon Dieu., Ils ne correspondent pas. . C'est égal à T La chaîne doit être S Avant la chaîne 40 Chaque position doit être jugée 10Une fois, Et a conclu à l'inadéquation ,Comme le montre la figure.


  Jusqu'au dernier 41Position, Parce que toutes les correspondances sont égales ,Il n'est donc pas nécessaire de continuer,Comme le montre la figure.S'il n'y a pas de substrats correspondants,Par exemple,T=“0000000002",On y est.41Il n'est pas non plus nécessaire de poursuivre la comparaison après l'inadéquation du jugement de position.La complexité temporelle du pire scénario est doncO((n-m+1)*m).

 En pratique,Pour les ordinateurs, Tout est binaire. 0Et1Chaîne, Un caractère ASCII Les codes peuvent aussi être considérés comme 8 Bits binaires 01Chaîne,Bien sûr.,Tous les caractères tels que les caractères chinois peuvent également être considérés comme plus d'un0Et1Chaîne.Comme l'infographie, par exemple, peut être compris comme un grand nombre de0Et1 Composition de la chaîne .Donc, dans l'informatique,L'opération Pattern Matching peut être considérée comme n'importe où, Et cet algorithme , C'est inefficace. .

/*  Méthode simple d'appariement des modèles  */
int Index(String S, String T, int pos) 
{
	int i = pos;	/* i Pour la chaîne principale S Indice de position actuel moyen ,SiposNon.1,Depos La position commence à correspondre  */
	int j = 1;				/* j Pour substrats T Indice de position actuel moyen  */
	while (i <= S[0] && j <= T[0]) /* SiiMoins deS Longueur et jMoins deT En longueur ,La boucle continue. */
	{
		if (S[i] == T[j]) 	/*  Deux lettres égales continuent  */
      	{
			++i;
         	++j; 
      	} 
      	else 				/* Le pointeur recule et recommence à correspondre */
      	{  
         	i = i-j+2;		/* iRetour à la première place de la dernière correspondance */
         	j = 1; 			/* j Retour au substrat TLa première */
      	}      
	}
	if (j > T[0]) 
		return i-T[0];
	else 
		return 0;
}

Trois,KPMAlgorithme de correspondance de modèle pour

Pouvez - vous supporter l'inefficacité de l'algorithme de correspondance de motif simple? Peut - être pas. 、 Ça n'a peut - être pas d'importance. .Mais il y a des années, nos scientifiques, J'ai l'impression qu'il y en a plusieurs comme ça. 0Et1 Chaîne de caractères dupliquée ,Mais l'algorithme qui nécessite une traversée individuelle est une très mauvaise chose. Il y avait donc trois aînés. ,D.E.Knuth、J.H.MorrisEt VR.Pratt(Parmi euxKnuth Et Pratt Recherche commune ,Morris Recherche indépendante )Publier un algorithme de correspondance de motifs,La répétition des traversées peut être grandement évitée,On l'appelle Knut— Algorithme Morris Pratt ,AbréviationsKMPAlgorithmes.

1,Principe de l'algorithme

Si la chaîne principale S=“abcdefgab”, Ça pourrait être plus long. ,On oublie juste de garder9Bits, On va faire une correspondance. T=“abcdex”,Donc, avec l'algorithme simple précédent,Avant5Les lettres, Les deux chaînes sont exactement égales ,Jusqu'au6Les lettres,“f”Avec“x”Attendez.,Comme indiqué①Comme indiqué.

Et puis...,Algorithme de correspondance en mode simple, Ça devrait être comme ça. ②③④⑤⑥. C'est - à - dire la chaîne principale SZhongdangi=2、3、4、5、6Heure, Premier caractère et sous - chaîne T Les premiers caractères de .
Comme si c'était normal. ,C'est ainsi que l'algorithme original a été conçu.. Peut être observé de près . Pour les substrats à apparier TDis,"abcdex”Les initiales“a” Avec la chaîne suivante “bcdex”Aucun des caractères n'est égal.C'est - à - dire,Puisque“a”N'est pas égal à l'un des caractères de la Sous - chaîne qui suit, Donc pour les graphiques, ①Dis, Les cinq premiers caractères sont égaux , Signifie substrat TPremier caractère de“a”Impossible avecS Numéro de la chaîne 2BIT à bit5 Les caractères des bits sont égaux .Dans le graphique,②③④⑤ Les jugements sont superflus. .
Notez qu'il s'agit de comprendre KMP La clé de l'algorithme .Si nous savonsT Premier caractère de la chaîne “a”AvecTAucun des caractères suivants n'est égal( C'est la prémisse. , Comment juger? ).EtT Deuxième position de la chaîne “b”AvecS Deuxième dans la chaîne “b” Dans la figure ①Déjà jugé égal,Donc ça veut dire,T Premier caractère de la chaîne “a”AvecS Deuxième dans la chaîne “b”Il n'y a pas besoin de jugement pour savoir qu'ils ne peuvent pas être égaux, Comme ça. ②Cette étape du jugement peut être omise,Comme indiqué ci - dessous.

 C'est la même chose., Avant que nous sachions T Premier caractère de la chaîne “a”AvecTSi les caractères suivants ne sont pas égaux,TString“a”AvecS Derrière la chaîne “c”、"d”、“e” Ou les deux. ①Après cela, on peut déterminer que ce n'est pas égal, Donc, dans cet algorithme, ②③④⑤C'est inutile.,Réservé uniquement①⑥C'est tout.,Comme le montre la figure.

Pourquoi? ⑥ Le jugement dans ①Moyenne T[6]≠S[6], Même si nous savons déjà T[1]≠T[6], Mais il n'est pas certain T[1] Ça ne doit pas être égal à S[6], Il faut donc les conserver. ⑥Cette étape.
Quelqu'un va demander,SiTLa chaîne est également suivie du premier caractère“a” Et les caractères de ?
Prenons l'exemple suivant,HypothèsesS=“abcabcabc”,T=“abcabx”. Jugement sur le début ,Avant5 Les caractères sont exactement égaux ,No6 Caractères différents ,Comme indiqué①.En ce moment, D'après l'expérience ,TPremier caractère de“a”AvecT Deuxième caractère de “b"、 Troisième caractère “℃” Non. , Pas besoin de jugement. , Étapes de l'algorithme simple du graphique ②③ C'est superflu. .


 

Parce queTLa première“a”AvecT Quatrième “a”Équivalence,Second“b” Avec la cinquième place “b”Équivalence.Et①Heure, Quatrième “a” Avec la cinquième place “b” Déjà avec la chaîne principale SLa position correspondante dans la comparaison est dépassée,Est égal,On peut donc conclure que,TPremier caractère de“a”、 Deuxième caractère “b”AvecS Quatrième chiffre de .

Le caractère et le cinquième caractère n'ont pas besoin d'être comparés, Ça doit être égal. —— C'est déjà fait. , De quoi juger? ,Alors...④⑤Les deux étapes de la comparaison pour obtenir des caractères égaux peuvent également être omises.
C'est - à - dire,Pour les caractères qui ont un caractère égal au premier caractère dans la Sous - chaîne,Il est également possible d'omettre certaines étapes de jugement inutiles.Comme le montre la figure, Omettre à droite T Les deux premiers chiffres de la chaîne “a”Avec“b”Même chose.SEn chaîne4、5 Opération de correspondance des caractères de position .

  Comparez ces deux exemples ,Nous découvrirons①Heure, Nos valeurs principales ,C'est - à - dire que l'indice de la position actuelle de la chaîne principale est6,23④5,iLa valeur est2、3、4、5,On y est.⑥,i Ça vaut le coup de revenir. 6.C'est - à - dire que dans l'algorithme simple de correspondance de motifs, Chaîne principale i Les valeurs sont constamment retracées pour être complétées. Et notre analyse a révélé ,Ce genre de rétrosuivi peut être inutile——C'est ce qu'on appelle un bon cheval qui ne mange pas d'herbe,La nôtre. KMPL'algorithme d'appariement des motifs est conçu pour empêcher ce retour en arrière inutile.
Puisque la valeur principale n'est pas retracée , C'est - à - dire qu'il ne peut pas être plus petit ,Alors le changement à considérer estjÇa vaut le coup.. L'observation montre également , Nous l'avons mentionné à maintes reprises. TComparaison du premier caractère d'une chaîne avec le caractère suivant, Trouvé s'il y a des caractères égaux ,j Les valeurs varient .C'est - à - dire,C'estjLe changement de valeur n'a rien à voir avec la chaîne principale, Ça dépend. TY a - t - il un problème de duplication dans la structure de la chaîne.
Comme dans le graphique,Parce queT="abcdex",Il n'y a pas de caractères en double,Alors...jJuste par6Est devenu1.Et dans le graphique,,Parce queT="abcabx",Préfixe“ab” Et enfin “x” Suffixe de la chaîne précédente “ab”Est égal.Donc,jJuste par6Est devenu3.Donc,, On peut trouver des règles. ,jLa valeur dépend de la similitude du préfixe de la chaîne avant le caractère courant.

2,NEXTDérivation du tableau

Comment déduire une chaîne denext Et la valeur du tableau? ,Voyons quelques exemples.
1.T="abcdex”(Comme indiqué dans le tableau)

1)Quand=1Heure,next[1]=0;

2)Quandj=2Heure,jPar1Àj-1 Juste des caractères. “a”,Autres situationsnext[2]=1;

3)Quandj=3Heure,jPar1Àj-1La chaîne est“ab”,Apparemment.“a”Avec“b”Pas égal, Autres circonstances ,next[3]=1;

4) Même chose à l'avenir. , Donc finalement, TStringnexti]Pour011111.

2. T="abcabx”(Comme indiqué dans le tableau)

1)Quandj=1Heure,next[1]=0;

2)Quandj=2Heure, Comme indiqué dans l'exemple précédent ,next[2]=1;3)Quandj=3Heure,Ibid.,next[3]=1;

4)Quandj=4Heure,Ibid.,next[4]=1;

5)Quandj=5Heure,En ce momentjPar1Àj-1 La chaîne est “abca”, Préfixe “a” Et suffixe
“a”Équivalence( Préfixe souligné , Suffixe en italique ), Il est donc possible de calculer kLa valeur est:2(Par‘pr…pk-1'-'P)j-ki1…p-1',Je l'ai.p1=p4)Donc,next[5]=2;

6)Quandj=6Heure,jPar1Àj-1 La chaîne est “abcab”, En raison du caractère préfixe “ab” Et suffixe “ab”
Équivalence,Alors...next[6]=3.

Peut être obtenu empiriquement si le préfixe est égal à un caractère,kLa valeur est2,Deux caractèreskLa valeur est3,

3.T="“ababaaaba"(Comme indiqué dans le tableau)

1)Quand=1Heure,next[1]=0;

2)Quandj=2Heure,Ibid.next[2]=1;

3)Quandj=3Heure,Ibid.next[3]=1;

4)Quandj=4Heure,jPar1Àj-1 La chaîne est “aba”, Préfixe “a” Et suffixe “a”Phase
Attendez.,next[4]=2;

5)Quandj=5Heure,jPar1Àj-1 La chaîne est “abab”, En raison du caractère préfixe “ab” Et suffixe “ab”
Équivalence,Alors...next[5]=3;

6)Quandj=6Heure,jPar1Àj-1 La chaîne est “ababa”, En raison du caractère préfixe “aba” Et suffixe
"abaӃquivalence,Alors...next[6]=4;

7)Quandj=7Heure,jPar1Àj-1 La chaîne est “ababaa”, En raison du caractère préfixe “ab” Et suffixe
“aa”Pas égal,Seulement“a”Équivalence,Alors...next[7]=2;

8)Quandj=8Heure,jPar1Àj-1 La chaîne est “ababaaa”,Seulement“a”Équivalence,Alors...
next[8]=2;

9)Quandj=9Heure,jPar1Àj-1 La chaîne est “ababaaab”, En raison du caractère préfixe “ab” Et suffixe
“ab”Équivalence,Alors...next[9]=3.

4, T="aaaaaaaab”(Comme indiqué dans le tableau)


 1)Quandj=1Heure,next[1]=0;

2)Quandj=2Heure,Ibid.next[2]=1;

3)Quandj=3Heure,jPar1Àj-1 La chaîne est “aa”, Préfixe “a” Et suffixe “a”Phase
Attendez.,next[3]=2;

4)Quandj=4Heure,jPar1Àj-1 La chaîne est “aaa”, En raison du caractère préfixe “aa” Et suffixe “aa”Phase
Attendez.,Alors...next[4]=3;

5) ..…..

6)Quandj=9Heure,jPar1Àj-1 La chaîne est “aaaaaaaa”, En raison du caractère préfixe “aaaaaaa” Et suffixe “aaaaaaa”Équivalence,Alors...next[9]=8.

3,Réalisation de l'algorithme

/*  Sous - chaîne retournée par calcul TDenextTableau. */
void get_next(String T, int *next) 
{
	int i,k;
  	i=1;
  	k=0;
  	next[1]=0;
  	while (i<T[0])  /* Ici.T[0]Chaîne de représentationTLongueur */
 	{
    	if(k==0 || T[i]== T[k]) 
		{
      		++i;  
			++k;  
			next[i] = k;
    	} 
		else 
			k= next[k];	/*  Si les caractères sont différents ,Etk Suivi de la valeur  */
  	}
}

/*  Renvoie le substrat TDans la chaîne principaleSMoyennepos Position après les caractères .S'il n'existe pas, La valeur de retour de la fonction est 0. */
/*  TNon vide,1≤pos≤StrLength(S). */
int Index_KMP(String S, String T, int pos) 
{
	int i = pos;		/* i Pour la chaîne principale S Indice de position actuel moyen ,SiposNon.1,Depos La position commence à correspondre  */
	int j = 1;			/* j Pour substrats T Indice de position actuel moyen  */
	int next[255];		/* Définition InextTableau */
	get_next(T, next);	/*  Paire de cordes T Analyse ,Je l'ai.nextTableau */
	while (i <= S[0] && j <= T[0]) /* SiiMoins deS Longueur et jMoins deT En longueur ,La boucle continue. */
	{
		if (j==0 || S[i] == T[j]) 	/*  Deux lettres égales continuent , Avec des algorithmes simples j=0Jugement */
      	{
         	++i;
         	++j; 
      	} 
      	else 			/* Le pointeur recule et recommence à correspondre */
      	 	j = next[j];/* j Retour à la bonne position ,iValeur constante */
	}
	if (j > T[0]) 
		return i-T[0];
	else 
	

4,Amélioration de l'algorithme

Pourget_nextEn fonction,SiTLa longueur dem,Parce qu'il ne s'agit que d'un simple cycle,Sa complexité temporelle est0(m), Et parce que la valeur principale n'est pas retracée ,De faire index_KMP Amélioration de l'efficacité de l'algorithme ,while La complexité temporelle du cycle est O(n).Donc,,La complexité temporelle de l'algorithme estO(n+m).Comparé à l'algorithme de correspondance de motif simpleO((n-m+1)*m)Dis, C'est mieux. .
Il convient également de souligner ici ,KMPAlgorithme seulement s'il y a beaucoup entre le mode et la chaîne principale“Correspondance partielle”C'est dans ce cas que ses avantages se manifestent,Sinon, la différence n'est pas évidente.

Et puis quelqu'un a découvert,KMP Toujours défectueux .Par exemple,, Si notre chaîne principale S="aaaabcde”,SubstratsT="aaaaax”",Lenext Les valeurs du tableau sont 012345,Au début,Quand i=5、j=5Heure,Nous avons découvertb”Avec“a”Pas égal,Comme indiqué①,Donc,j=next[5]=4,Comme le montre la figure②,En ce moment“b”Et4Localisation“a” Toujours pas. ,j=next[4]=3,Comme le montre la figure③, Et puis... ④⑥,Jusqu'àj=next[1]=0Heure, Selon l'algorithme ,En ce momenti++、j++,Je l'ai. i=6、j=1,Comme le montre la figure⑥.

Nous avons découvert,Au milieu②③④⑤Étapes, C'est un jugement superflu. .Parce queT Deuxième de la chaîne 、Trois、Quatre、Les caractères à cinq positions sont les premiers“a”Équivalence, Donc vous pouvez utiliser le premier next[1]Pour remplacer les caractères qui lui sont équivalents parnext[i]Valeur de, C'est une bonne idée. . C'est pourquoi nous demandons next Fonction modifiée .
Supposons que le tableau remplacé soit nextval, Ajout d'une section en gras ,Les codes sont les suivants::

/* Trouver la chaîne de modeTDenextLa fonction corrige les valeurs et les stocke dans le tableaunextval */
void get_nextval(String T, int *nextval) 
{
  	int i,k;
  	i=1;
  	k=0;
  	nextval[1]=0;
  	while (i<T[0])  /* Ici.T[0]Chaîne de représentationTLongueur */
 	{
    	if(k==0 || T[i]== T[k]) 	/* T[i] Un seul caractère représentant un suffixe ,T[k] Un seul caractère représentant le préfixe  */
		{
      		++i;  
			++k;  
			if (T[i]!=T[k])      /* Si le caractère courant est différent du caractère préfixe */
				nextval[i] = k;	/* Alors le courantjPournextvalIniValeur de la position */
      		else 
				nextval[i] = nextval[k];	/*  Si le même caractère préfixe , Préfixer le caractère  */
											/* nextvalValeur attribuée ànextvalIniValeur de la position */
    	} 
		else 
			k= nextval[k];			/*  Si les caractères sont différents ,Etk Suivi de la valeur  */
  	}
}

Quatre,Tous les codes

#include "string.h"
#include "stdio.h"    
#include "stdlib.h"   

#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* Allocation initiale de stockage */

typedef int Status;		/* StatusEst le type de fonction,Sa valeur est le Code d'état du résultat de la fonction,Par exemple:OKAttendez. */
typedef int ElemType;	/* ElemTypeType selon la situation réelle,Supposons ici queint */

typedef char String[MAXSIZE+1]; /*  0 Unit é # longueur de la chaîne de stockage  */

/*  Générer une valeur égale à charsChaîneT */
Status StrAssign(String T,char *chars)
{ 
	int i;
	if(strlen(chars)>MAXSIZE)
		return ERROR;
	else
	{
		T[0]=strlen(chars);
		for(i=1;i<=T[0];i++)
			T[i]=*(chars+i-1);
		return OK;
	}
}

Status ClearString(String S)
{ 
	S[0]=0;/*   Faire la longueur de la chaîne à zéro  */
	return OK;
}

/*  Chaîne de sortieT. */
void StrPrint(String T)
{ 
	int i;
	for(i=1;i<=T[0];i++)
		printf("%c",T[i]);
	printf("\n");
}

/*  ProduitsNextValeur du tableau. */
void NextPrint(int next[],int length)
{ 
	int i;
	for(i=1;i<=length;i++)
		printf("%d",next[i]);
	printf("\n");
}

/*  Renvoie le nombre d'éléments de la chaîne  */
int StrLength(String S)
{ 
	return S[0];
}

/*  Méthode simple d'appariement des modèles  */
int Index(String S, String T, int pos) 
{
	int i = pos;	/* i Pour la chaîne principale S Indice de position actuel moyen ,SiposNon.1,Depos La position commence à correspondre  */
	int j = 1;				/* j Pour substrats T Indice de position actuel moyen  */
	while (i <= S[0] && j <= T[0]) /* SiiMoins deS Longueur et jMoins deT En longueur ,La boucle continue. */
	{
		if (S[i] == T[j]) 	/*  Deux lettres égales continuent  */
      	{
			++i;
         	++j; 
      	} 
      	else 				/* Le pointeur recule et recommence à correspondre */
      	{  
         	i = i-j+2;		/* iRetour à la première place de la dernière correspondance */
         	j = 1; 			/* j Retour au substrat TLa première */
      	}      
	}
	if (j > T[0]) 
		return i-T[0];
	else 
		return 0;
}

/*  Sous - chaîne retournée par calcul TDenextTableau. */
void get_next(String T, int *next) 
{
	int i,k;
  	i=1;
  	k=0;
  	next[1]=0;
  	while (i<T[0])  /* Ici.T[0]Chaîne de représentationTLongueur */
 	{
    	if(k==0 || T[i]== T[k]) 
		{
      		++i;  
			++k;  
			next[i] = k;
    	} 
		else 
			k= next[k];	/*  Si les caractères sont différents ,Etk Suivi de la valeur  */
  	}
}

/*  Renvoie le substrat TDans la chaîne principaleSMoyennepos Position après les caractères .S'il n'existe pas, La valeur de retour de la fonction est 0. */
/*  TNon vide,1≤pos≤StrLength(S). */
int Index_KMP(String S, String T, int pos) 
{
	int i = pos;		/* i Pour la chaîne principale S Indice de position actuel moyen ,SiposNon.1,Depos La position commence à correspondre  */
	int j = 1;			/* j Pour substrats T Indice de position actuel moyen  */
	int next[255];		/* Définition InextTableau */
	get_next(T, next);	/*  Paire de cordes T Analyse ,Je l'ai.nextTableau */
	while (i <= S[0] && j <= T[0]) /* SiiMoins deS Longueur et jMoins deT En longueur ,La boucle continue. */
	{
		if (j==0 || S[i] == T[j]) 	/*  Deux lettres égales continuent , Avec des algorithmes simples j=0Jugement */
      	{
         	++i;
         	++j; 
      	} 
      	else 			/* Le pointeur recule et recommence à correspondre */
      	 	j = next[j];/* j Retour à la bonne position ,iValeur constante */
	}
	if (j > T[0]) 
		return i-T[0];
	else 
		return 0;
}

/* Trouver la chaîne de modeTDenextLa fonction corrige les valeurs et les stocke dans le tableaunextval */
void get_nextval(String T, int *nextval) 
{
  	int i,k;
  	i=1;
  	k=0;
  	nextval[1]=0;
  	while (i<T[0])  /* Ici.T[0]Chaîne de représentationTLongueur */
 	{
    	if(k==0 || T[i]== T[k]) 	/* T[i] Un seul caractère représentant un suffixe ,T[k] Un seul caractère représentant le préfixe  */
		{
      		++i;  
			++k;  
			if (T[i]!=T[k])      /* Si le caractère courant est différent du caractère préfixe */
				nextval[i] = k;	/* Alors le courantjPournextvalIniValeur de la position */
      		else 
				nextval[i] = nextval[k];	/*  Si le même caractère préfixe , Préfixer le caractère  */
											/* nextvalValeur attribuée ànextvalIniValeur de la position */
    	} 
		else 
			k= nextval[k];			/*  Si les caractères sont différents ,Etk Suivi de la valeur  */
  	}
}

int Index_KMP1(String S, String T, int pos) 
{
	int i = pos;		/* i Pour la chaîne principale S Indice de position actuel moyen ,SiposNon.1,Depos La position commence à correspondre  */
	int j = 1;			/* j Pour substrats T Indice de position actuel moyen  */
	int next[255];		/* Définition InextTableau */
	get_nextval(T, next);	/*  Paire de cordes T Analyse ,Je l'ai.nextTableau */
	while (i <= S[0] && j <= T[0]) /* SiiMoins deS Longueur et jMoins deT En longueur ,La boucle continue. */
	{
		if (j==0 || S[i] == T[j]) 	/*  Deux lettres égales continuent , Avec des algorithmes simples j=0Jugement */
      	{
         	++i;
         	++j; 
      	} 
      	else 			/* Le pointeur recule et recommence à correspondre */
      	 	j = next[j];/* j Retour à la bonne position ,iValeur constante */
	}
	if (j > T[0]) 
		return i-T[0];
	else 
		return 0;
}

int main()
{
	int i,*p;
	String s1,s2;
	
	StrAssign(s1,"abcdex");
	printf(" Le substrat est : ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("NextPour: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"abcabx");
	printf(" Le substrat est : ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("NextPour: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"ababaaaba");
	printf(" Le substrat est : ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("NextPour: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"aaaaaaaab");
	printf(" Le substrat est : ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("NextPour: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"ababaaaba");
	printf("    Le substrat est : ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("   NextPour: ");
	NextPrint(p,StrLength(s1));
	get_nextval(s1,p); 
	printf("NextValPour: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"aaaaaaaab");
	printf("    Le substrat est : ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("   NextPour: ");
	NextPrint(p,StrLength(s1));
	get_nextval(s1,p); 
	printf("NextValPour: ");
	NextPrint(p,StrLength(s1));

	printf("\n");

	StrAssign(s1,"00000000000000000000000000000000000000000000000001");
	printf(" La chaîne principale est : ");
	StrPrint(s1);
	StrAssign(s2,"0000000001");
	printf(" Le substrat est : ");
	StrPrint(s2);
	printf("\n");
	printf(" Les chaînes principales et les sous - chaînes sont %d Première correspondance aux caractères ( Algorithme de correspondance de modèle simple )\n",Index(s1,s2,1));
	printf(" Les chaînes principales et les sous - chaînes sont %d Première correspondance aux caractères (KMPAlgorithmes) \n",Index_KMP(s1,s2,1));
	printf(" Les chaînes principales et les sous - chaînes sont %d Première correspondance aux caractères (KMP Algorithme amélioré ) \n",Index_KMP1(s1,s2,1));

	return 0;
}

Cinq, Remarques finales

Si vous voyez ici, Demande de commentaires ,Votre triple compagnie est la plus grande force motrice de mes progrès!!!
 

版权声明
本文为[- Non.]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211013211336214d.html

Scroll to Top