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