Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

58
LINES

< > BotCompany Repo | #1028143 // BoyerMooreStringSearch_upper

JavaX fragment (include) [tags: use-pretranspiled]

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  
}

Author comment

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: 149 / 424
Referenced in: [show references]