Discussion :

[kam42]

Bonjour à tous ;
je travaille sur un algorithme de recherche de motif dans un texte qui s'appelle " Boyer-Moore" . Le probleme est qu'il marche pour des motifs dont la taille est superieure ou egal à 3. pour un motif dont la taille est inferieure à 3, il m'affiche le Debug erreure suivant:

"stack around the variable ' tablesuffixes ' was corrupted"


voici mon programme:

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
void calculersauts(string motif, int tablesauts[])
{
	int longueurmotif=motif.length();
for(int i=0; i<256; i++)
  tablesauts[i]=longueurmotif;
for(int i=0; i<longueurmotif-1; i++)
  tablesauts[motif[i]]=longueurmotif-i-1;
}
 
void calculersuffixes(string motif, int suffixes[])
{
	int longueurmotif=motif.length();
	int iprec,index;
	suffixes[longueurmotif-1]=longueurmotif;
	index=longueurmotif-1;
	for(int i=longueurmotif-2; i>=0;i--)
	{
		if(i>index && suffixes[i+longueurmotif-1-iprec]<i-index)
			suffixes[i]=suffixes[i+longueurmotif-1-iprec];
		else
		{
			if(i<index)
				index=1;
			iprec=1;
			while(index>=0 && motif[index]==motif[index+longueurmotif-1-iprec])
				index--;
			suffixes[i]=iprec-index;
		}
	}
}
 
void calculertablesuffixes(string motif, int tablesuffixes[])
{
 
	int suffixes[100];
	int longueurmotif=motif.length();
	calculersuffixes(motif,suffixes);
	for(int i=0;i<longueurmotif;i++)
		tablesuffixes[i]=longueurmotif;
	int j=0;
	for(int i=longueurmotif-1;i>=-1;i--)
		if(i==-1||suffixes[i]==i+1)
			for(j=0 ; j<longueurmotif-1-i ; j++)
				if(tablesuffixes[j]==longueurmotif)
					tablesuffixes[j]=longueurmotif-1-i;
	for(int i=0; i<=longueurmotif-2;i++)
		tablesuffixes[longueurmotif-1-suffixes[i]]=longueurmotif-1-i;
}
 
int BoyerMoore(string motif,string texte)
{
	int i ;
	int tablesuffixes[100];
	int tablesauts[256];
	int longueurmotif=motif.length();
	int longueurtexte=texte.length();
	calculersauts(motif,tablesauts);
	calculertablesuffixes(motif,tablesuffixes);
	int j=0;
	while(j<=longueurtexte-longueurmotif)
	{
		for(i=longueurmotif-1;i>=0 && motif[i]==texte[i+j];i--);
		if(i<0)
		{
			return j;
		}
		else
		{
			unsigned char carac=texte[i+j];
			j += max(tablesuffixes[i],(tablesauts[carac]-longueurmotif+1+i));
 
		}
	}
	return -1;
}

merci d'avance !
[EDIT]
balise code ajouté par mongaulois

[Pacorabanix]

Pourrais tu aider à mettre sur la voie en nous disant à quel endroit du code l'erreur se produit ? avec un debugger ou au pire avec des std::cout << "Ok..." << ... bien placés .

D'autre part, un conseil pour la performance (et la propreté du code) mais qui ne réglera pas ton problème : les string que tu passes en argument à tes fonctions ne sont jamais modifiées, donc tu peux remplacer les arguments string argument par const string & argument.