1 | sclass BoyerMoore_chars {
|
2 | final static int R = 256; // the radix |
3 | final int[] right; // the bad-character skip array |
4 | final char[] pat; // pattern |
5 | |
6 | *(S pat) { this(toCharArray(pat)); }
|
7 | |
8 | *(char[] *pat) {
|
9 | // position of rightmost occurrence of c in the pattern |
10 | right = new int[R]; |
11 | for (int j = 0; j < pat.length; j++) |
12 | right[pat[j] & (R-1)] = j+1; |
13 | } |
14 | |
15 | /** |
16 | * Returns the index of the first occurrrence of the pattern string |
17 | * in the text string. |
18 | * |
19 | * @param txt the text string |
20 | * @return the index of the first occurrence of the pattern string |
21 | * in the text string; -1 if no such match |
22 | */ |
23 | int search(char[] txt) {
|
24 | if (txt == null) ret -1; |
25 | int m = pat.length; |
26 | int n = txt.length; |
27 | int skip; |
28 | for (int i = 0; i <= n - m; i += skip) {
|
29 | skip = 0; |
30 | for (int j = m-1; j >= 0; j--) {
|
31 | if (pat[j] != txt[i+j]) {
|
32 | skip = Math.max(1, j - (right[txt[i+j] & (R-1)]-1)); |
33 | break; |
34 | } |
35 | } |
36 | if (skip == 0) ret i; |
37 | } |
38 | ret -1; |
39 | } |
40 | } |
Began life as a copy of #1013280
download show line numbers debug dex old transpilations
Travelled to 8 computer(s): bhatertpkbcr, cfunsshuasjs, gwrvuhgaqvyk, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt
No comments. add comment
| Snippet ID: | #1020539 |
| Snippet name: | BoyerMoore_chars - boyer-moore search on char arrays |
| Eternal ID of this version: | #1020539/1 |
| Text MD5: | db0ba67caded6d70e31d4ce8563aacfd |
| Author: | stefan |
| Category: | javax |
| Type: | JavaX fragment (include) |
| Public (visible to everyone): | Yes |
| Archived (hidden from active list): | No |
| Created/modified: | 2018-12-26 01:02:50 |
| Source code size: | 1130 bytes / 40 lines |
| Pitched / IR pitched: | No / No |
| Views / Downloads: | 311 / 816 |
| Referenced in: | [show references] |