Libraryless. Click here for Pure Java version (3833L/25K).
1 | /** |
2 | * Finds the first occurrence of a pattern string |
3 | * in a text string. Converts all to uppercase. |
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_upper {
|
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(upper(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 = upper(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 #1013280
download show line numbers debug dex old transpilations
Travelled to 7 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt, xrpafgyirdlv
No comments. add comment
| Snippet ID: | #1028143 |
| Snippet name: | BoyerMooreStringSearch_upper |
| Eternal ID of this version: | #1028143/1 |
| Text MD5: | 2982c1902fdbd2d10349ad910ad1a875 |
| Transpilation MD5: | 6e55b662e16c3d5791c101961a93af2d |
| 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:14:18 |
| Source code size: | 1770 bytes / 58 lines |
| Pitched / IR pitched: | No / No |
| Views / Downloads: | 217 / 531 |
| Referenced in: | [show references] |