Libraryless. Click here for Pure Java version (3826L/25K).
1 | /** |
2 | * Finds the first occurrence of a pattern string |
3 | * in a text string. |
4 | * <p> |
5 | * This implementation uses the Boyer-Moore algorithm (with the bad-character |
6 | * rule, but not the strong good suffix rule). |
7 | * <p> |
8 | * For additional documentation, |
9 | * see <a href="https://algs4.cs.princeton.edu/53substring">Section 5.3</a> of |
10 | * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. |
11 | * Copyright © 2000–2017, Robert Sedgewick and Kevin Wayne. |
12 | * Last updated: Fri Oct 20 12:50:46 EDT 2017. |
13 | */ |
14 | sclass BoyerMooreStringSearch {
|
15 | final static int R = 256; // the radix |
16 | final int[] right; // the bad-character skip array |
17 | final char[] pat; // pattern |
18 | |
19 | *(S pat) {
|
20 | this.pat = toCharArray(pat); |
21 | |
22 | // position of rightmost occurrence of c in the pattern |
23 | right = new int[R]; |
24 | for (int j = 0; j < this.pat.length; j++) |
25 | right[this.pat[j] & (R-1)] = j+1; |
26 | } |
27 | |
28 | /** |
29 | * Returns the index of the first occurrrence of the pattern string |
30 | * in the text string. |
31 | * |
32 | * @param txt the text string |
33 | * @return the index of the first occurrence of the pattern string |
34 | * in the text string; -1 if no such match |
35 | */ |
36 | int search(S txt) {
|
37 | if (txt == null) ret -1; |
38 | int m = pat.length; |
39 | int diff = txt.length()-m; |
40 | int skip; |
41 | for (int i = 0; i <= diff; i += skip) {
|
42 | skip = 0; |
43 | for (int j = m-1; j >= 0; j--) {
|
44 | int c = txt.charAt(i+j); |
45 | if (pat[j] != c) {
|
46 | skip = Math.max(1, j - (right[c & (R-1)]-1)); |
47 | break; |
48 | } |
49 | } |
50 | if (skip == 0) ret i; |
51 | } |
52 | ret -1; |
53 | } |
54 | |
55 | bool containedIn(S txt) {
|
56 | ret search(txt) >= 0; |
57 | } |
58 | } |
Began life as a copy of #1013279
download show line numbers debug dex old transpilations
Travelled to 14 computer(s): aoiabmzegqzx, bhatertpkbcr, cbybwowwnfue, cfunsshuasjs, gwrvuhgaqvyk, ishqpsrjomds, lpdgvwnxivlt, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tslmcundralx, tvejysmllsmz, vouqrxazstgt, xrpafgyirdlv
No comments. add comment
| Snippet ID: | #1013280 |
| Snippet name: | BoyerMooreStringSearch |
| Eternal ID of this version: | #1013280/14 |
| Text MD5: | 8777b5ffa28fc7662d008e425c030d24 |
| Transpilation MD5: | 3b3d5c653f76db94c6cc1af2bd5c7a32 |
| Author: | stefan |
| Category: | javax |
| Type: | JavaX fragment (include) |
| Public (visible to everyone): | Yes |
| Archived (hidden from active list): | No |
| Created/modified: | 2020-05-23 14:13:14 |
| Source code size: | 1726 bytes / 58 lines |
| Pitched / IR pitched: | No / No |
| Views / Downloads: | 462 / 1118 |
| Version history: | 13 change(s) |
| Referenced in: | [show references] |