Implémentation algo boyer moore

Bonjour à tous,

J'ai un petit souci avec un algo de string matching que je n'arrive pas à implémenté.
J'ai trouvé des code en c mais, rien à faire, je ne comprends pas une partie et je ne veux pas recopier un code que je ne comprends pas mais le faire par moi même.

Voici le code :

Code:

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
 
void preBmBc(char *x, int m, int bmBc[]) { 
   int i; 
 
   for (i = 0; i < ASIZE; ++i) 
      bmBc[i] = m; 
   for (i = 0; i < m - 1; ++i) 
      bmBc[x[i]] = m - i - 1; 
} 
 
 
void suffixes(char *x, int m, int *suff) { 
   int f, g, i; 
 
   suff[m - 1] = m; 
   g = m - 1; 
   for (i = m - 2; i >= 0; --i) { 
      if (i > g && suff[i + m - 1 - f] < i - g) 
         suff[i] = suff[i + m - 1 - f]; 
      else { 
         if (i < g) 
            g = i; 
         f = i; 
         while (g >= 0 && x[g] == x[g + m - 1 - f]) 
            --g; 
         suff[i] = f - g; 
      } 
   } 
} 
 
void preBmGs(char *x, int m, int bmGs[]) { 
   int i, j, suff[XSIZE]; 
 
   suffixes(x, m, suff); 
 
   for (i = 0; i < m; ++i) 
      bmGs[i] = m; 
   j = 0; 
   for (i = m - 1; i >= 0; --i) 
      if (suff[i] == i + 1) 
         for (; j < m - 1 - i; ++j) 
            if (bmGs[j] == m) 
               bmGs[j] = m - 1 - i; 
   for (i = 0; i <= m - 2; ++i) 
      bmGs[m - 1 - suff[i]] = m - 1 - i; 
} 
 
 
void BM(char *x, int m, char *y, int n) { 
   int i, j, bmGs[XSIZE], bmBc[ASIZE]; 
 
   /* Preprocessing */ 
   preBmGs(x, m, bmGs); 
   preBmBc(x, m, bmBc); 
 
   /* Searching */ 
   j = 0; 
   while (j <= n - m) { 
      for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i); 
      if (i < 0) { 
         OUTPUT(j); 
         j += bmGs[0]; 
      } 
      else 
         j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i); 
   } 
}

Ce que je ne comprends pas c'est la partie suffixes et preBmGs. J'ai compris le principe de l'algo mais pas son implémentation. Donc si quelqu'un pouvait m'éclairer ca serait pas mal!

Voila, merci d'avance pour votre aide :)