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;
} |
