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 (8 years ago) by gpertea
File size: 2641 byte(s)
Log Message:
wip

Line User Rev File contents
1 gpertea 99 #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     }