Java Dizgi Eşleme Algoritmaları
Apostolico-Crochemore algoritması
|
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
import java.util.ArrayList;
import java.util.List;
public class AC {
private static void preKmp(char[] x, int[] kmpNext) {
int i, j, m = (x.length - 1);
i = 0;
j = kmpNext[0] = -1;
while (i < m) {
while (j > -1 && x[i] != x[j])
j = kmpNext[j];
i++;
j++;
if (x[i] == x[j])
kmpNext[i] = kmpNext[j];
else
kmpNext[i] = j;
}
}
public static List<Integer> findAll(String pattern, String source) {
char[] ptrn = pattern.toCharArray(), y = source.toCharArray();
char[] x = new char[ptrn.length + 1];
System.arraycopy(ptrn, 0, x, 0, ptrn.length);
int i, j, k, ell, m = ptrn.length, n = y.length;
List<Integer> result = new ArrayList<Integer>();
int[] kmpNext = new int[x.length];
/* Preprocessing */
preKmp(x, kmpNext);
for (ell = 1; x[ell - 1] == x[ell]; ell++)
;
if (ell == m)
ell = 0;
/* Searching */
i = ell;
j = k = 0;
while (j <= n - m) {
while (i < m && x[i] == y[i + j])
++i;
if (i >= m) {
while (k < ell && x[k] == y[j + k])
++k;
if (k >= ell)
result.add(j);
}
j += (i - kmpNext[i]);
if (i == ell)
k = Math.max(0, k - 1);
else if (kmpNext[i] <= ell) {
k = Math.max(0, kmpNext[i]);
i = ell;
} else {
k = ell;
i = kmpNext[i];
}
}
return result;
}
public static AC compile(String pattern) {
char[] ptrn = pattern.toCharArray();
char[] x = new char[ptrn.length + 1];
System.arraycopy(ptrn, 0, x, 0, ptrn.length);
int ell, m = ptrn.length;
int[] kmpNext = new int[x.length];
preKmp(x, kmpNext);
for (ell = 1; x[ell - 1] == x[ell]; ell++)
;
if (ell == m)
ell = 0;
AC ac = new AC();
ac.m = m;
ac.ell = ell;
ac.x = x;
ac.kmpNext = kmpNext;
return ac;
}
public List<Integer> findAll(String source) {
char[] y = source.toCharArray();
int i, j, k, n = y.length;
List<Integer> result = new ArrayList<Integer>();
i = ell;
j = k = 0;
while (j <= n - m) {
while (i < m && x[i] == y[i + j])
++i;
if (i >= m) {
while (k < ell && x[k] == y[j + k])
++k;
if (k >= ell)
result.add(j);
}
j += (i - kmpNext[i]);
if (i == ell)
k = Math.max(0, k - 1);
else if (kmpNext[i] <= ell) {
k = Math.max(0, kmpNext[i]);
i = ell;
} else {
k = ell;
i = kmpNext[i];
}
}
return result;
}
private int m, ell;
private char[] x;
private int[] kmpNext;
}
|
Apostolico-Giancarlo algoritması
|
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
import java.util.ArrayList;
import java.util.List;
public class AG {
private static void preBmBc(char[] x, int bmBc[]) {
int i, m = x.length;
for (i = 0; i < bmBc.length; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
private static void suffixes(char[] x, int[] suff) {
int f = 0, g, i, m = x.length;
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;
}
}
}
private static void preBmGs(char[] x, int bmGs[], int[] suff) {
int i, j, m = x.length;
suffixes(x, 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;
}
private static void arrayCpy(int[] trg, int trgIdx, int[] src, int srcIdx,
int length) {
for (int i = 0; i < length; i++)
trg[trgIdx + i] = src[srcIdx + i];
}
public static List<Integer> findAll(String pattern, String source) {
char[] x = pattern.toCharArray(), y = source.toCharArray();
int i, j, k, s, shift, m = x.length, n = y.length;
List<Integer> result = new ArrayList<Integer>();
int[] bmGs = new int[m];
int[] skip = new int[m];
int[] suff = new int[m];
int[] bmBc = new int[65536];
/* Preprocessing */
preBmGs(x, bmGs, suff);
preBmBc(x, bmBc);
for (i = 0; i < m; i++)
skip[i] = 0;
/* Searching */
j = 0;
while (j <= n - m) {
i = m - 1;
while (i >= 0) {
k = skip[i];
s = suff[i];
if (k > 0)
if (k > s) {
if (i + 1 == s)
i = (-1);
else
i -= s;
break;
} else {
i -= k;
if (k < s)
break;
}
else {
if (x[i] == y[i + j])
--i;
else
break;
}
}
if (i < 0) {
result.add(j);
skip[m - 1] = m;
shift = bmGs[0];
} else {
skip[m - 1] = m - 1 - i;
shift = Math.max(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
j += shift;
arrayCpy(skip, 0, skip, shift, (m - shift));
for (i = 0; i < shift; i++)
skip[m - shift + i] = 0;
}
return result;
}
public static AG compile(String pattern) {
char[] x = pattern.toCharArray();
int i, m = x.length;
int[] bmGs = new int[m];
int[] skip = new int[m];
int[] suff = new int[m];
int[] bmBc = new int[65536];
preBmGs(x, bmGs, suff);
preBmBc(x, bmBc);
for (i = 0; i < m; i++)
skip[i] = 0;
AG ag = new AG();
ag.bmGs = bmGs;
ag.skip = skip;
ag.suff = suff;
ag.bmBc = bmBc;
ag.x = x;
ag.m = m;
return ag;
}
public List<Integer> findAll(String source) {
char[] y = source.toCharArray();
int i, j, k, s, shift, n = y.length;
List<Integer> result = new ArrayList<Integer>();
j = 0;
while (j <= n - m) {
i = m - 1;
while (i >= 0) {
k = skip[i];
s = suff[i];
if (k > 0)
if (k > s) {
if (i + 1 == s)
i = (-1);
else
i -= s;
break;
} else {
i -= k;
if (k < s)
break;
}
else {
if (x[i] == y[i + j])
--i;
else
break;
}
}
if (i < 0) {
result.add(j);
skip[m - 1] = m;
shift = bmGs[0];
} else {
skip[m - 1] = m - 1 - i;
shift = Math.max(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
j += shift;
arrayCpy(skip, 0, skip, shift, (m - shift));
for (i = 0; i < shift; i++)
skip[m - shift + i] = 0;
}
return result;
}
private int[] bmGs, skip, suff, bmBc;
private char[] x;
private int m;
}
|
Brute Force algoritması
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
import java.util.ArrayList;
import java.util.List;
public class BF {
public static List<Integer> findAll(String pattern, String source) {
char[] x = pattern.toCharArray(), y = source.toCharArray();
int i, j, m = x.length, n = y.length;
List<Integer> result = new ArrayList<Integer>();
/* Searching */
for (j = 0; j <= n - m; ++j) {
for (i = 0; i < m && x[i] == y[i + j]; ++i)
;
if (i >= m)
result.add(j);
}
return result;
}
}
|
Boyer-Moore algorithması
|
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
import java.util.ArrayList;
import java.util.List;
public class BM {
private static void preBmBc(char[] x, int bmBc[]) {
int i, m = x.length;
for (i = 0; i < bmBc.length; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
private static void suffixes(char[] x, int[] suff) {
int f = 0, g, i, m = x.length;
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;
}
}
}
private static void preBmGs(char[] x, int bmGs[]) {
int i, j, m = x.length;
int[] suff = new int[m];
suffixes(x, 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;
}
public static List<Integer> findAll(String pattern, String source) {
char[] x = pattern.toCharArray(), y = source.toCharArray();
int i, j, m = x.length, n = y.length;
List<Integer> result = new ArrayList<Integer>();
int[] bmGs = new int[m];
int[] bmBc = new int[65536];
/* Preprocessing */
preBmGs(x, bmGs);
preBmBc(x, bmBc);
/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i)
;
if (i < 0) {
result.add(j);
j += bmGs[0];
} else
j += Math.max(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
return result;
}
public static BM compile(String pattern) {
char[] x = pattern.toCharArray();
int m = x.length;
int[] bmGs = new int[m];
int[] bmBc = new int[65536];
preBmGs(x, bmGs);
preBmBc(x, bmBc);
BM bm = new BM();
bm.bmBc = bmBc;
bm.bmGs = bmGs;
bm.x = x;
bm.m = m;
return bm;
}
public List<Integer> findAll(String source) {
char[] y = source.toCharArray();
int i, j, n = y.length;
List<Integer> result = new ArrayList<Integer>();
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i)
;
if (i < 0) {
result.add(j);
j += bmGs[0];
} else
j += Math.max(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
return result;
}
private int[] bmGs, bmBc;
private char[] x;
private int m;
}
|
Backward Nondeterministic Dawg Matching algoritması
|
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
import java.util.ArrayList;
import java.util.List;
public class BNDM {
public static List<Integer> findAll(String pattern, String source) {
char[] x = pattern.toCharArray(), y = source.toCharArray();
int i, j, s, d, last, m = x.length, n = y.length;
List<Integer> result = new ArrayList<Integer>();
int[] b = new int[65536];
/* Pre processing */
for (i = 0; i < b.length; i++)
b[i] = 0;
s = 1;
for (i = m - 1; i >= 0; i--) {
b[x[i]] |= s;
s <<= 1;
}
/* Searching phase */
j = 0;
while (j <= n - m) {
i = m - 1;
last = m;
d = ~0;
while (i >= 0 && d != 0) {
d &= b[y[j + i]];
i--;
if (d != 0) {
if (i >= 0)
last = i + 1;
else
result.add(j);
}
d <<= 1;
}
j += last;
}
return result;
}
public static BNDM compile(String pattern) {
char[] x = pattern.toCharArray();
int i, s, m = x.length;
int[] b = new int[65536];
for (i = 0; i < b.length; i++)
b[i] = 0;
s = 1;
for (i = m - 1; i >= 0; i--) {
b[x[i]] |= s;
s <<= 1;
}
BNDM bndm = new BNDM();
bndm.m = m;
bndm.b = b;
return bndm;
}
public List<Integer> findAll(String source) {
char[] y = source.toCharArray();
int i, j, d, last, n = y.length;
List<Integer> result = new ArrayList<Integer>();
j = 0;
while (j <= n - m) {
i = m - 1;
last = m;
d = ~0;
while (i >= 0 && d != 0) {
d &= b[y[j + i]];
i--;
if (d != 0) {
if (i >= 0)
last = i + 1;
else
result.add(j);
}
d <<= 1;
}
j += last;
}
return result;
}
private int[] b;
private int m;
}
|
Backward Oracle Matching algoritması
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
import java.util.ArrayList;
import java.util.List;
public class BOM {
private static final char TRUE = 1;
private static final char FALSE = 0;
private static final int UNDEFINED = -1;
private static int getTransition(char[] x, int p, Cell[] list, char c) {
Cell cell;
if (p > 0 && x[p - 1] == c)
return (p - 1);
else {
cell = list[p];
while (cell != null)
if (x
|
|
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
[cell.element] == c)
return (cell.element);
else
cell = cell.next;
return (UNDEFINED);
}
}
private static void setTransition(int p, int q, Cell[] list) {
Cell cell = new Cell();
cell.element = q;
cell.next = list[p];
list[p] = cell;
}
private static void oracle(char[] x, char[] t, Cell[] list) {
int i, p, q = UNDEFINED, m = x.length - 1;
int[] s = new int[x.length];
char c;
s[m] = m + 1;
for (i = m; i > 0; --i) {
c = x[i - 1];
p = s[i];
while (p <= m && (q = getTransition(x, p, list, c)) == UNDEFINED) {
setTransition(p, i - 1, list);
p = s[p];
}
s[i - 1] = (p == m + 1 ? m : q);
}
p = 0;
while (p <= m) {
t[p] = TRUE;
p = s[p];
}
}
public static List findAll(String pattern, String source) {
char[] ptrn = pattern.toCharArray(), y = source.toCharArray();
char[] x = new char[ptrn.length + 1];
System.arraycopy(ptrn, 0, x, 0, ptrn.length);
int i, j, p, period = 0, q, shift, m = ptrn.length, n = y.length;
List result = new ArrayList();
char[] t = new char[x.length];
Cell[] list = new Cell[x.length];
/* Preprocessing */
for (i = 0; i < t.length; i++)
t[i] = FALSE;
oracle(x, t, list);
/* Searching */
j = 0;
while (j = 0
&& (q = getTransition(x, p, list, y[i + j])) != UNDEFINED) {
p = q;
if (t[p] == TRUE) {
period = shift;
shift = i;
}
--i;
}
if (i < 0) {
result.add(j);
shift = period;
}
j += shift;
}
return result;
}
public static BOM compile(String pattern) {
char[] ptrn = pattern.toCharArray();
char[] x = new char[ptrn.length + 1];
System.arraycopy(ptrn, 0, x, 0, ptrn.length);
int i, m = ptrn.length;
char[] t = new char[x.length];
Cell[] list = new Cell[x.length];
for (i = 0; i < t.length; i++)
t[i] = FALSE;
oracle(x, t, list);
BOM bom = new BOM();
bom.m = m;
bom.x = x;
bom.t = t;
bom.list = list;
return bom;
}
public List findAll(String source) {
char[] y = source.toCharArray();
int i, j, p, period = 0, q, shift, n = y.length;
List result = new ArrayList();
j = 0;
while (j = 0
&& (q = getTransition(x, p, list, y[i + j])) != UNDEFINED) {
p = q;
if (t[p] == TRUE) {
period = shift;
shift = i;
}
--i;
}
if (i < 0) {
result.add(j);
shift = period;
}
j += shift;
}
return result;
}
private char[] x, t;
private Cell[] list;
private int m;
private static class Cell {
int element;
Cell next;
}
}
|
Berry-Ravindran algoritması
|
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
import java.util.ArrayList;
import java.util.List;
public class BR {
private static void preBrBc(char[] x, int[][] brBc) {
int a, b, i, m = x.length;
for (a = 0; a < brBc.length; ++a)
for (b = 0; b < brBc.length; ++b)
brBc[a][b] = m + 2;
for (a = 0; a < brBc.length; ++a)
brBc[a][x[0]] = m + 1;
for (i = 0; i < m - 1; ++i)
brBc[x[i]][x[i + 1]] = m - i;
for (a = 0; a < brBc.length; ++a)
brBc[x[m - 1]][a] = 1;
}
private static int arrayCmp(char[] a, int aIdx, char[] b, int bIdx,
int length) {
int i = 0;
for (i = 0; i < length && aIdx + i < a.length && bIdx + i < b.length; i++) {
if (a[aIdx + i] == b[bIdx + i])
;
else if (a[aIdx + i] > b[bIdx + i])
return 1;
else
return 2;
}
if (i < length)
if (a.length - aIdx == b.length - bIdx)
return 0;
else if (a.length - aIdx > b.length - bIdx)
return 1;
else
return 2;
else
return 0;
}
private static int calculateBrBcSize(char[] x, char[] y) {
int i;
char maxChar = 0;
for (i = 0; i < x.length; i++)
if (x[i] > maxChar)
maxChar = x[i];
for (i = 0; i < y.length; i++)
if (y[i] > maxChar)
maxChar = y[i];
maxChar++;
return maxChar;
}
public static List<Integer> findAll(String pattern, String source) {
char[] x = pattern.toCharArray(), src = source.toCharArray();
char[] y = new char[src.length + 2];
System.arraycopy(src, 0, y, 0, src.length);
int j, m = x.length, n = src.length;
List<Integer> result = new ArrayList<Integer>();
if(calculateBrBcSize(x, src) > 256)
return null;
int[][] brBc = new int[256][256];
/* Preprocessing */
preBrBc(x, brBc);
/* Searching */
j = 0;
y[n + 1] = '\0';
while (j < n - m) {
if (arrayCmp(x, 0, y, j, m) == 0)
result.add(j);
j += brBc[y[j + m]][y[j + m + 1]];
}
if(j == n - m && arrayCmp(x, 0, y, j, m) == 0)
result.add(j);
return result;
}
public static BR compile(String pattern) {
char[] x = pattern.toCharArray();
int m = x.length;
int[][] brBc = new int[256][256];
preBrBc(x, brBc);
BR br = new BR();
br.brBc = brBc;
br.m = m;
br.x = x;
return br;
}
public List<Integer> findAll(String source) {
char[] src = source.toCharArray();
char[] y = new char[src.length + 2];
System.arraycopy(src, 0, y, 0, src.length);
int j, n = src.length;
List<Integer> result = new ArrayList<Integer>();
if(calculateBrBcSize(x, src) > 256)
return null;
j = 0;
y[n + 1] = '\0';
while (j < n - m) {
if (arrayCmp(x, 0, y, j, m) == 0)
result.add(j);
j += brBc[y[j + m]][y[j + m + 1]];
}
if(j == n - m && arrayCmp(x, 0, y, j, m) == 0)
result.add(j);
return result;
}
private char[] x;
private int m;
private int[][] brBc;
}
|
|
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
import java.util.ArrayList;
import java.util.List;
public class CLS {
private static int preColussi(char[] x, int[] h, int[] next, int[] shift) {
int i, k, nd, q, r = 0, s, m = (x.length - 1);
int[] hmax = new int[x.length];
int[] kmin = new int[x.length];
int[] nhd0 = new int[x.length];
int[] rmin = new int[x.length];
/* Computation of hmax */
i = k = 1;
do {
while (x[i] == x[i - k])
i++;
hmax[k] = i;
q = k + 1;
while (hmax[q - k] + k < i) {
hmax[q] = hmax[q - k] + k;
q++;
}
k = q;
if (k == i + 1)
i = k;
} while (k <= m);
/* Computation of kmin */
for (i = 0; i < m; i++)
kmin[i] = 0;
for (i = m; i >= 1; --i)
if (hmax[i] < m)
kmin[hmax[i]] = i;
/* Computation of rmin */
for (i = m - 1; i >= 0; --i) {
if (hmax[i + 1] == m)
r = i + 1;
if (kmin[i] == 0)
rmin[i] = r;
else
rmin[i] = 0;
}
/* Computation of h */
s = -1;
r = m;
for (i = 0; i < m; ++i)
if (kmin[i] == 0)
h[--r] = i;
else
h[++s] = i;
nd = s;
/* Computation of shift */
for (i = 0; i <= nd; ++i)
shift[i] = kmin[h[i]];
for (i = nd + 1; i < m; ++i)
shift[i] = rmin[h[i]];
shift[m] = rmin[0];
/* Computation of nhd0 */
s = 0;
for (i = 0; i < m; ++i) {
nhd0[i] = s;
if (kmin[i] > 0)
++s;
}
/* Computation of next */
for (i = 0; i <= nd; ++i)
next[i] = nhd0[h[i] - kmin[h[i]]];
for (i = nd + 1; i < m; ++i)
next[i] = nhd0[m - rmin[h[i]]];
next[m] = nhd0[m - rmin[h[m - 1]]];
return (nd);
}
public static List<Integer> findAll(String pattern, String source) {
char[] ptrn = pattern.toCharArray(), y = source.toCharArray();
char[] x = new char[ptrn.length + 1];
System.arraycopy(ptrn, 0, x, 0, ptrn.length);
int i, j, last, nd, m = ptrn.length, n = y.length;
List<Integer> result = new ArrayList<Integer>();
int[] h = new int[x.length];
int[] next = new int[x.length];
int[] shift = new int[x.length];
/* Processing */
nd = preColussi(x, h, next, shift);
/* Searching */
i = j = 0;
last = -1;
while (j <= n - m) {
while (i < m && last < j + h[i] && x[h[i]] == y[j + h[i]])
i++;
if (i >= m || last >= j + h[i]) {
result.add(j);
i = m;
}
if (i > nd)
last = j + m - 1;
j += shift[i];
i = next[i];
}
return result;
}
public static CLS compile(String pattern) {
char[] ptrn = pattern.toCharArray();
char[] x = new char[ptrn.length + 1];
System.arraycopy(ptrn, 0, x, 0, ptrn.length);
int nd, m = ptrn.length;
int[] h = new int[x.length];
int[] next = new int[x.length];
int[] shift = new int[x.length];
/* Processing */
nd = preColussi(x, h, next, shift);
CLS cls = new CLS();
cls.x = x;
cls.h = h;
cls.m = m;
cls.next = next;
cls.shift = shift;
cls.nd = nd;
return cls;
}
public List<Integer> findAll(String source) {
char[] y = source.toCharArray();
int i, j, last, n = y.length;
List<Integer> result = new ArrayList<Integer>();
i = j = 0;
last = -1;
while (j <= n - m) {
while (i < m && last < j + h[i] && x[h[i]] == y[j + h[i]])
i++;
if (i >= m || last >= j + h[i]) {
result.add(j);
i = m;
}
if (i > nd)
last = j + m - 1;
j += shift[i];
i = next[i];
}
return result;
}
private char[] x;
private int[] h, next, shift;
private int nd, m;
}
|
Deterministic Finite Automaton algoritması
|
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
|
import java.util.ArrayList;
import java.util.List;
public class DFA {
private static void preAut(char[] x, Graph aut) {
int i, state, target, oldTarget, m = x.length;
for (state = Automata.getInitial(aut), i = 0; i < m; ++i) {
oldTarget = Automata.getTarget(aut, state, x[i]);
target = Automata.newVertex(aut);
Automata.setTarget(aut, state, x[i], target);
Automata.copyVertex(aut, target, oldTarget);
state = target;
}
Automata.setTerminal(aut, state);
}
public static List<Integer> findAll(String pattern, String source) {
char[] x = pattern.toCharArray(), y = source.toCharArray();
int j, state, m = x.length, n = y.length;
List<Integer> result = new ArrayList<Integer>();
Graph aut;
/* Preprocessing */
aut = Automata.newAutomaton(m + 1, (m + 1) * 65536);
preAut(x, aut);
/* Searching */
for (state = Automata.getInitial(aut), j = 0; j < n; ++j) {
state = Automata.getTarget(aut, state, y[j]);
if (Automata.isTerminal(aut, state))
result.add(j - m + 1);
}
return result;
}
public static DFA compile(String pattern) {
char[] x = pattern.toCharArray();
int m = x.length;
Graph aut;
aut = Automata.newAutomaton(m + 1, (m + 1) * 65536);
preAut(x, aut);
DFA dfa = new DFA();
dfa.aut = aut;
dfa.m = m;
return dfa;
}
public List<Integer> findAll(String source) {
char[] y = source.toCharArray();
int j, state, n = y.length;
List<Integer> result = new ArrayList<Integer>();
for (state = Automata.getInitial(aut), j = 0; j < n; ++j) {
state = Automata.getTarget(aut, state, y[j]);
if (Automata.isTerminal(aut, state))
result.add(j - m + 1);
}
return result;
}
private Graph aut;
private int m;
private static class Graph {
private int vertexNumber, edgeNumber, vertexCounter, initial;
private int[] terminal, target, suffixLink, length, position, shift;
}
private static class Automata {
private static final int UNDEFINED = -1;
/*
* returns a new data structure for a graph with v vertices and e edges
*/
public static Graph newGraph(int v, int e) {
Graph g = new Graph();
g.vertexNumber = v;
g.edgeNumber = e;
g.initial = 0;
g.vertexCounter = 1;
return (g);
}
/*
* returns a new data structure for a automaton with v vertices and e
* edges
*/
public static Graph newAutomaton(int v, int e) {
Graph aut;
aut = newGraph(v, e);
aut.target = new int[e];
;
aut.terminal = new int[v];
return (aut);
}
/*
* returns a new data structure for a suffix automaton with v vertices
* and e edges
*/
public static Graph newSuffixAutomaton(int v, int e) {
Graph aut;
aut = newAutomaton(v, e);
aut.target = new int[e];
for (int i = 0; i < e; i++)
aut.target[i] = UNDEFINED;
aut.suffixLink = new int[v];
aut.length = new int[v];
aut.position = new int[v];
aut.shift = new int[e];
return (aut);
}
/*
* returns a new data structure for a trie with v vertices and e edges
*/
public static Graph newTrie(int v, int e) {
Graph aut;
aut = newAutomaton(v, e);
aut.target = new int[e];
for (int i = 0; i < e; i++)
aut.target[i] = UNDEFINED;
aut.suffixLink = new int[v];
aut.length = new int[v];
aut.position = new int[v];
aut.shift = new int[e];
return (aut);
}
/* returns a new vertex for graph g */
public static int newVertex(Graph g) {
int res = -1;
if (g != null && g.vertexCounter <= g.vertexNumber)
res = (g.vertexCounter++);
return res;
}
/* returns the initial vertex of graph g */
public static int getInitial(Graph g) {
return g.initial;
}
/* returns true if vertex v is terminal in graph g */
public static boolean isTerminal(Graph g, int v) {
boolean res = false;
if (g != null && g.terminal != null && v < g.vertexNumber)
res = (g.terminal[v] == 1 ? true : false);
return res;
}
/* set vertex v to be terminal in graph g */
public static void setTerminal(Graph g, int v) {
if (g != null && g.terminal != null && v < g.vertexNumber)
g.terminal[v] = 1;
}
/*
* returns the target of edge from vertex v labelled by character c in
* graph g
*/
public static int getTarget(Graph g, int v, int c) {
int res = -1;
if (g != null && g.target != null && v < g.vertexNumber
&& v * c < g.edgeNumber)
res = (g.target[v * (g.edgeNumber / g.vertexNumber) + c]);
return res;
}
/*
* add the edge from vertex v to vertex t labelled by character c in
* graph g
*/
public static void setTarget(Graph g, int v, int c, int t) {
if (g != null && g.target != null && v < g.vertexNumber
&& v * c <= g.edgeNumber && t < g.vertexNumber)
g.target[v * (g.edgeNumber / g.vertexNumber) + c] = t;
}
/* returns the suffix link of vertex v in graph g */
public static int getSuffixLink(Graph g, int v) {
int res = -1;
if (g != null && g.suffixLink != null && v < g.vertexNumber)
res = (g.suffixLink[v]);
return res;
}
/*
* set the suffix link of vertex v to vertex s in graph g
*/
public static void setSuffixLink(Graph g, int v, int s) {
if (g != null && g.suffixLink != null && v < g.vertexNumber
&& s < g.vertexNumber)
g.suffixLink[v] = s;
}
/* returns the length of vertex v in graph g */
public static int getLength(Graph g, int v) {
int res = -1;
if (g != null && g.length != null && v < g.vertexNumber)
res = (g.length[v]);
return res;
}
/* set the length of vertex v to integer ell in graph g */
public static void setLength(Graph g, int v, int ell) {
if (g != null && g.length != null && v < g.vertexNumber)
g.length[v] = ell;
}
/* returns the position of vertex v in graph g */
public static int getPosition(Graph g, int v) {
int res = -1;
if (g != null && g.position != null && v < g.vertexNumber)
res = (g.position[v]);
return res;
}
/* set the length of vertex v to integer ell in graph g */
public static void setPosition(Graph g, int v, int p) {
if (g != null && g.position != null && v < g.vertexNumber)
g.position[v] = p;
}
/*
* returns the shift of the edge from vertex v labelled by character c
* in graph g
*/
public static int getShift(Graph g, int v, int c) {
int res = -1;
if (g != null && g.shift != null && v < g.vertexNumber
&& v * c < g.edgeNumber)
res = (g.shift[v * (g.edgeNumber / g.vertexNumber) + c]);
return res;
}
/*
* set the shift of the edge from vertex v labelled by character c to
* integer s in graph g
*/
public static void setShift(Graph g, int v, int c, int s) {
if (g != null && g.shift != null && v < g.vertexNumber
&& v * c <= g.edgeNumber)
g.shift[v * (g.edgeNumber / g.vertexNumber) + c] = s;
}
/*
* copies all the characteristics of vertex source to vertex target in
* graph g
*/
public static void copyVertex(Graph g, int target, int source) {
if (g != null && target < g.vertexNumber && source < g.vertexNumber) {
if (g.target != null)
for (int i = 0; i < (g.edgeNumber / g.vertexNumber); i++)
g.target[target * (g.edgeNumber / g.vertexNumber) + i] = g.target[source 1="(g.edgeNumber" 2="/" 3="g.vertexNumber)" 4="+" 5="i" language="*"][/source];
if (g.shift != null)
for (int i = 0; i < (g.edgeNumber / g.vertexNumber); i++)
g.shift[target * (g.edgeNumber / g.vertexNumber) + i] = g.shift[source 1="(g.edgeNumber" 2="/" 3="g.vertexNumber)" 4="+" 5="i" language="*"][/source];
if (g.terminal != null)
g.terminal[target] = g.terminal[source][/source];
if (g.suffixLink != null)
g.suffixLink[target] = g.suffixLink[source][/source];
if (g.length != null)
g.length[target] = g.length[source][/source];
if (g.position != null)
g.position[target] = g.position[source][/source];
}
}
}
}
|
Forward Dawg Matching algoritması
|
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
|
import java.util.ArrayList;
import java.util.List;
public class FDM {
private static void buildSuffixAutomaton(char[] x, Graph aut) {
int i, art, init, last, p, q, r, m = x.length;
char c;
init = Automata.getInitial(aut);
art = Automata.newVertex(aut);
Automata.setSuffixLink(aut, init, art);
last = init;
for (i = 0; i < m; ++i) {
c = x[i];
p = last;
q = Automata.newVertex(aut);
Automata.setLength(aut, q, Automata.getLength(aut, p) + 1);
Automata.setPosition(aut, q, Automata.getPosition(aut, p) + 1);
while (p != init
&& Automata.getTarget(aut, p, c) == Automata.UNDEFINED) {
Automata.setTarget(aut, p, c, q);
Automata.setShift(aut, p, c, Automata.getPosition(aut, q)
- Automata.getPosition(aut, p) - 1);
p = Automata.getSuffixLink(aut, p);
}
if (Automata.getTarget(aut, p, c) == Automata.UNDEFINED) {
Automata.setTarget(aut, init, c, q);
Automata.setShift(aut, init, c, Automata.getPosition(aut, q)
- Automata.getPosition(aut, init) - 1);
Automata.setSuffixLink(aut, q, init);
} else if (Automata.getLength(aut, p) + 1 == Automata.getLength(
aut, Automata.getTarget(aut, p, c)))
Automata.setSuffixLink(aut, q, Automata.getTarget(aut, p, c));
else {
r = Automata.newVertex(aut);
Automata.copyVertex(aut, r, Automata.getTarget(aut, p, c));
Automata.setLength(aut, r, Automata.getLength(aut, p) + 1);
Automata.setSuffixLink(aut, Automata.getTarget(aut, p, c), r);
Automata.setSuffixLink(aut, q, r);
while (p != art
&& Automata.getLength(aut, Automata
.getTarget(aut, p, c)) >= Automata.getLength(
aut, r)) {
Automata.setShift(aut, p, c, Automata.getPosition(aut,
Automata.getTarget(aut, p, c))
- Automata.getPosition(aut, p) - 1);
Automata.setTarget(aut, p, c, r);
p = Automata.getSuffixLink(aut, p);
}
}
last = q;
}
Automata.setTerminal(aut, last);
while (last != init) {
last = Automata.getSuffixLink(aut, last);
Automata.setTerminal(aut, last);
}
}
public static List<Integer> findAll(String pattern, String source) {
char[] x = pattern.toCharArray(), y = source.toCharArray();
int j, init, ell, state, m = x.length, n = y.length;
List<Integer> result = new ArrayList<Integer>();
Graph aut;
/* Preprocessing */
aut = Automata.newSuffixAutomaton(2 * (m + 2), 2 * (m + 2)
* 65536);
buildSuffixAutomaton(x, aut);
init = Automata.getInitial(aut);
/* Searching */
ell = 0;
state = init;
for (j = 0; j < n; ++j) {
if (Automata.getTarget(aut, state, y[j]) != Automata.UNDEFINED) {
++ell;
state = Automata.getTarget(aut, state, y[j]);
} else {
while (state != init
&& Automata.getTarget(aut, state, y[j]) == Automata.UNDEFINED)
state = Automata.getSuffixLink(aut, state);
if (Automata.getTarget(aut, state, y[j]) != Automata.UNDEFINED) {
ell = Automata.getLength(aut, state) + 1;
state = Automata.getTarget(aut, state, y[j]);
} else {
ell = 0;
state = init;
}
}
if (ell == m)
result.add(j - m + 1);
}
return result;
}
public static FDM compile(String pattern) {
char[] x = pattern.toCharArray();
int init, m = x.length;
Graph aut;
aut = Automata.newSuffixAutomaton(2 * (m + 2), 2 * (m + 2)
* 65536);
buildSuffixAutomaton(x, aut);
init = Automata.getInitial(aut);
FDM fdm = new FDM();
fdm.aut = aut;
fdm.m = m;
fdm.init = init;
return fdm;
}
public List<Integer> findAll(String source) {
char[] y = source.toCharArray();
int j, ell, state, n = y.length;
List<Integer> result = new ArrayList<Integer>();
ell = 0;
state = init;
for (j = 0; j < n; ++j) {
if (Automata.getTarget(aut, state, y[j]) != Automata.UNDEFINED) {
++ell;
state = Automata.getTarget(aut, state, y[j]);
} else {
while (state != init
&& Automata.getTarget(aut, state, y[j]) == Automata.UNDEFINED)
state = Automata.getSuffixLink(aut, state);
if (Automata.getTarget(aut, state, y[j]) != Automata.UNDEFINED) {
ell = Automata.getLength(aut, state) + 1;
state = Automata.getTarget(aut, state, y[j]);
} else {
ell = 0;
state = init;
}
}
if (ell == m)
result.add(j - m + 1);
}
return result;
}
private Graph aut;
private int m, init;
private static class Graph {
private int vertexNumber, edgeNumber, vertexCounter, initial;
private int[] terminal, target, suffixLink, length, position, shift;
}
private static class Automata {
private static final int UNDEFINED = -1;
/*
* returns a new data structure for a graph with v vertices and e edges
*/
public static Graph newGraph(int v, int e) {
Graph g = new Graph();
g.vertexNumber = v;
g.edgeNumber = e;
g.initial = 0;
g.vertexCounter = 1;
return (g);
}
/*
* returns a new data structure for a automaton with v vertices and e
* edges
*/
public static Graph newAutomaton(int v, int e) {
Graph aut;
aut = newGraph(v, e);
aut.target = new int[e];
;
aut.terminal = new int[v];
return (aut);
}
/*
* returns a new data structure for a suffix automaton with v vertices
* and e edges
*/
public static Graph newSuffixAutomaton(int v, int e) {
Graph aut;
aut = newAutomaton(v, e);
aut.target = new int[e];
for (int i = 0; i < e; i++)
aut.target[i] = UNDEFINED;
aut.suffixLink = new int[v];
aut.length = new int[v];
aut.position = new int[v];
aut.shift = new int[e];
return (aut);
}
/*
* returns a new data structure for a trie with v vertices and e edges
*/
public static Graph newTrie(int v, int e) {
Graph aut;
aut = newAutomaton(v, e);
aut.target = new int[e];
for (int i = 0; i < e; i++)
aut.target[i] = UNDEFINED;
aut.suffixLink = new int[v];
aut.length = new int[v];
aut.position = new int[v];
aut.shift = new int[e];
return (aut);
}
/* returns a new vertex for graph g */
public static int newVertex(Graph g) {
int res = -1;
if (g != null && g.vertexCounter <= g.vertexNumber)
res = (g.vertexCounter++);
return res;
}
/* returns the initial vertex of graph g */
public static int getInitial(Graph g) {
return g.initial;
}
/* returns true if vertex v is terminal in graph g */
public static boolean isTerminal(Graph g, int v) {
boolean res = false;
if (g != null && g.terminal != null && v < g.vertexNumber)
res = (g.terminal[v] == 1 ? true : false);
return res;
}
/* set vertex v to be terminal in graph g */
public static void setTerminal(Graph g, int v) {
if (g != null && g.terminal != null && v < g.vertexNumber)
g.terminal[v] = 1;
}
/*
* returns the target of edge from vertex v labelled by character c in
* graph g
*/
public static int getTarget(Graph g, int v, int c) {
int res = -1;
if (g != null && g.target != null && v < g.vertexNumber
&& v * c < g.edgeNumber)
res = (g.target[v * (g.edgeNumber / g.vertexNumber) + c]);
return res;
}
/*
* add the edge from vertex v to vertex t labelled by character c in
* graph g
*/
public static void setTarget(Graph g, int v, int c, int t) {
if (g != null && g.target != null && v < g.vertexNumber
&& v * c <= g.edgeNumber && t < g.vertexNumber)
g.target[v * (g.edgeNumber / g.vertexNumber) + c] = t;
}
/* returns the suffix link of vertex v in graph g */
public static int getSuffixLink(Graph g, int v) {
int res = -1;
if (g != null && g.suffixLink != null && v < g.vertexNumber)
res = (g.suffixLink[v]);
return res;
}
/*
* set the suffix link of vertex v to vertex s in graph g
*/
public static void setSuffixLink(Graph g, int v, int s) {
if (g != null && g.suffixLink != null && v < g.vertexNumber
&& s < g.vertexNumber)
g.suffixLink[v] = s;
}
/* returns the length of vertex v in graph g */
public static int getLength(Graph g, int v) {
int res = -1;
if (g != null && g.length != null && v < g.vertexNumber)
res = (g.length[v]);
return res;
}
/* set the length of vertex v to integer ell in graph g */
public static void setLength(Graph g, int v, int ell) {
if (g != null && g.length != null && v < g.vertexNumber)
g.length[v] = ell;
}
/* returns the position of vertex v in graph g */
public static int getPosition(Graph g, int v) {
int res = -1;
if (g != null && g.position != null && v < g.vertexNumber)
res = (g.position[v]);
return res;
}
/* set the length of vertex v to integer ell in graph g */
public static void setPosition(Graph g, int v, int p) {
if (g != null && g.position != null && v < g.vertexNumber)
g.position[v] = p;
}
/*
* returns the shift of the edge from vertex v labelled by character c
* in graph g
*/
public static int getShift(Graph g, int v, int c) {
int res = -1;
if (g != null && g.shift != null && v < g.vertexNumber
&& v * c < g.edgeNumber)
res = (g.shift[v * (g.edgeNumber / g.vertexNumber) + c]);
return res;
}
/*
* set the shift of the edge from vertex v labelled by character c to
* integer s in graph g
*/
public static void setShift(Graph g, int v, int c, int s) {
if (g != null && g.shift != null && v < g.vertexNumber
&& v * c <= g.edgeNumber)
g.shift[v * (g.edgeNumber / g.vertexNumber) + c] = s;
}
/*
* copies all the characteristics of vertex source to vertex target in
* graph g
*/
public static void copyVertex(Graph g, int target, int source) {
if (g != null && target < g.vertexNumber && source < g.vertexNumber) {
if (g.target != null)
for (int i = 0; i < (g.edgeNumber / g.vertexNumber); i++)
g.target[target * (g.edgeNumber / g.vertexNumber) + i] = g.target[source 1="(g.edgeNumber" 2="/" 3="g.vertexNumber)" 4="+" 5="i" language="*"][/source];
if (g.shift != null)
for (int i = 0; i < (g.edgeNumber / g.vertexNumber); i++)
g.shift[target * (g.edgeNumber / g.vertexNumber) + i] = g.shift[source 1="(g.edgeNumber" 2="/" 3="g.vertexNumber)" 4="+" 5="i" language="*"][/source];
if (g.terminal != null)
g.terminal[target] = g.terminal[source][/source];
if (g.suffixLink != null)
g.suffixLink[target] = g.suffixLink[source][/source];
if (g.length != null)
g.length[target] = g.length[source][/source];
if (g.position != null)
g.position[target] = g.position[source][/source];
}
}
}
}
|
Galil-Giancarlo algoritması
|
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
|
import java.util.ArrayList;
import java.util.List;
public class GG {
private static int preColussi(char[] x, int[] h, int[] next, int[] shift) {
int i, k, nd, q, r = 0, s, m = (x.length - 1);
int[] hmax = new int[x.length];
int[] kmin = new int[x.length];
int[] nhd0 = new int[x.length];
int[] rmin = new int[x.length];
/* Computation of hmax */
i = k = 1;
do {
while (x[i] == x[i - k])
i++;
hmax[k] = i;
q = k + 1;
while (hmax[q - k] + k < i) {
hmax[q] = hmax[q - k] + k;
q++;
}
k = q;
if (k == i + 1)
i = k;
} while (k <= m);
/* Computation of kmin */
for (i = 0; i < kmin.length; i++)
kmin[i] = 0;
for (i = m; i >= 1; --i)
if (hmax[i] < m)
kmin[hmax[i]] = i;
/* Computation of rmin */
for (i = m - 1; i >= 0; --i) {
if (hmax[i + 1] == m)
r = i + 1;
if (kmin[i] == 0)
rmin[i] = r;
else
rmin[i] = 0;
}
/* Computation of h */
s = -1;
r = m;
for (i = 0; i < m; ++i)
if (kmin[i] == 0)
h[--r] = i;
else
h[++s] = i;
nd = s;
/* Computation of shift */
for (i = 0; i <= nd; ++i)
shift[i] = kmin[h[i]];
for (i = nd + 1; i < m; ++i)
shift[i] = rmin[h[i]];
shift[m] = rmin[0];
/* Computation of nhd0 */
s = 0;
for (i = 0; i < m; ++i) {
nhd0[i] = s;
if (kmin[i] > 0)
++s;
}
/* Computation of next */
for (i = 0; i <= nd; ++i)
next[i] = nhd0[h[i] - kmin[h[i]]];
for (i = nd + 1; i < m; ++i)
next[i] = nhd0[m - rmin[h[i]]];
next[m] = nhd0[m - rmin[h[m - 1]]];
return (nd);
}
public static List<Integer> findAll(String pattern, String source) {
char[] ptrn = pattern.toCharArray(), y = source.toCharArray();
char[] x = new char[ptrn.length + 1];
System.arraycopy(ptrn, 0, x, 0, ptrn.length);
int i, j, k, ell, last, nd, m = ptrn.length, n = y.length;
List<Integer> result = new ArrayList<Integer>();
int[] h = new int[x.length];
int[] next = new int[x.length];
int[] shift = new int[x.length];
boolean heavy = false;
for (ell = 0; x[ell] == x[ell + 1]; ell++)
;
if (ell == m - 1)
/* Searching for a power of a single character */
for (j = ell = 0; j < n; ++j)
if (x[0] == y[j]) {
++ell;
if (ell >= m)
result.add(j - m + 1);
} else
ell = 0;
else {
/* Preprocessing */
nd = preColussi(x, h, next, shift);
/* Searching */
i = j = 0;
last = -1;
while (j <= n - m) {
if (heavy && i == 0) {
k = last - j + 1;
while (x[0] == y[j + k])
k++;
if (k <= ell || x[ell + 1] != y[j + k]) {
i = 0;
j += (k + 1);
last = j - 1;
} else {
i = 1;
last = j + k;
j = last - (ell + 1);
}
heavy = false;
} else {
while (i < m && last < j + h[i] && x[h[i]] == y[j + h[i]])
++i;
if (i >= m || last >= j + h[i]) {
result.add(j);
i = m;
}
if (i > nd)
last = j + m - 1;
j += shift[i];
i = next[i];
}
heavy = (j > last ? false : true);
}
}
return result;
}
public static GG compile(String pattern) {
char[] ptrn = pattern.toCharArray();
char[] x = new char[ptrn.length + 1];
System.arraycopy(ptrn, 0, x, 0, ptrn.length);
int nd, m = ptrn.length;
int[] h = new int[x.length];
|