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).

/**
 *  Finds the first occurrence of a pattern string
 *  in a text string. Converts all to uppercase.
 *  <p>
 *  This implementation uses the Boyer-Moore algorithm (with the bad-character
 *  rule, but not the strong good suffix rule).
 *  <p>
 *  For additional documentation,
 *  see <a href="https://algs4.cs.princeton.edu/53substring">Section 5.3</a> of
 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *  Copyright © 2000–2017, Robert Sedgewick and Kevin Wayne. 
 *  Last updated: Fri Oct 20 12:50:46 EDT 2017.
 */
sclass BoyerMooreStringSearch_upper {
  final static int R = 256;     // the radix
  final int[] right;     // the bad-character skip array
  final char[] pat;      // pattern

  *(S pat) {
    this.pat = toCharArray(upper(pat));

    // position of rightmost occurrence of c in the pattern
    right = new int[R];
    for (int j = 0; j < this.pat.length; j++)
        right[this.pat[j] & (R-1)] = j+1;
  }

  /**
   * Returns the index of the first occurrrence of the pattern string
   * in the text string.
   *
   * @param  txt the text string
   * @return the index of the first occurrence of the pattern string
   *         in the text string; -1 if no such match
   */
  int search(S txt) {
 if (txt == null) ret -1;
    int m = pat.length;
    int diff = txt.length()-m;
    int skip;
    for (int i = 0; i <= diff; i += skip) {
      skip = 0;
      for (int j = m-1; j >= 0; j--) {
        int c = upper(txt.charAt(i+j));
        if (pat[j] != c) {
          skip = Math.max(1, j - (right[c & (R-1)]-1));
          break;
        }
      }
      if (skip == 0) ret i;
    }
    ret -1;
  }
  
  bool containedIn(S txt) {
    ret search(txt) >= 0;
  }
}

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: 147 / 422
Referenced in: #1034167 - Standard Classes + Interfaces (LIVE, continuation of #1003674)