ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/bmsearch.cpp
Revision: 99
Committed: Thu Oct 6 20:49:17 2011 UTC (7 years, 8 months ago) by gpertea
File size: 2641 byte(s)
Log Message:
wip

Line File contents
1 #include "GBase.h"
2 #include "bmsearch.h"
3
4 void BMSearch::preBmBc(char *x, int m, int bmBc[]) {
5 int i;
6 for (i = 0; i < ASIZE; ++i)
7 bmBc[i] = m;
8 for (i = 0; i < m - 1; ++i)
9 bmBc[x[i]] = m - i - 1;
10 }
11
12
13 void BMSearch::suffixes(char *x, int m, int *suff) {
14 int f, g, i;
15 suff[m - 1] = m;
16 g = m - 1;
17 for (i = m - 2; i >= 0; --i) {
18 if (i > g && suff[i + m - 1 - f] < i - g)
19 suff[i] = suff[i + m - 1 - f];
20 else {
21 if (i < g)
22 g = i;
23 f = i;
24 while (g >= 0 && x[g] == x[g + m - 1 - f])
25 --g;
26 suff[i] = f - g;
27 }
28 }
29 }
30
31 void BMSearch::preBmGs(char *x, int m, int bmGs[]) {
32 int i, j, suff[XSIZE];
33
34 this->suffixes(x, m, suff);
35
36 for (i = 0; i < m; ++i)
37 bmGs[i] = m;
38 j = 0;
39 for (i = m - 1; i >= 0; --i)
40 if (suff[i] == i + 1)
41 for (; j < m - 1 - i; ++j)
42 if (bmGs[j] == m)
43 bmGs[j] = m - 1 - i;
44 for (i = 0; i <= m - 2; ++i)
45 bmGs[m - 1 - suff[i]] = m - 1 - i;
46 }
47
48
49 void BMSearch::search(char *x, int m, char *y, int n) {
50 int i, j, bmGs[XSIZE], bmBc[ASIZE];
51
52 /* Preprocessing */
53 this->preBmGs(x, m, bmGs);
54 this->preBmBc(x, m, bmBc);
55
56 /* Searching */
57 j = 0;
58 while (j <= n - m) {
59 for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
60 if (i < 0) {
61 OUTPUT(j);
62 j += bmGs[0];
63 }
64 else
65 j += GMAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
66 }
67 }
68
69 //In the Turbo BM function, the variable u memorizes the length of the
70 // suffix matched during the previous attempt and the variable v
71 // memorizes the length of the suffix matched during the current attempt.
72
73 void BMSearch::tsearch(char *x, int m, char *y, int n) {
74 int bcShift, i, j, shift, u, v, turboShift,
75 bmGs[XSIZE], bmBc[ASIZE];
76
77 /* Preprocessing */
78 this->preBmGs(x, m, bmGs);
79 this->preBmBc(x, m, bmBc);
80
81 /* Searching */
82 j = u = 0;
83 shift = m;
84 while (j <= n - m) {
85 i = m - 1;
86 while (i >= 0 && x[i] == y[i + j]) {
87 --i;
88 if (u != 0 && i == m - 1 - shift)
89 i -= u;
90 }
91 if (i < 0) {
92 OUTPUT(j);
93 shift = bmGs[0];
94 u = m - shift;
95 }
96 else {
97 v = m - 1 - i;
98 turboShift = u - v;
99 bcShift = bmBc[y[i + j]] - m + 1 + i;
100 shift = MAX(turboShift, bcShift);
101 shift = MAX(shift, bmGs[i]);
102 if (shift == bmGs[i])
103 u = MIN(m - shift, v);
104 else {
105 if (turboShift < bcShift)
106 shift = MAX(shift, u + 1);
107 u = 0;
108 }
109 }
110 j += shift;
111 }
112 }