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

40
LINES

< > BotCompany Repo | #1020539 // BoyerMoore_chars - boyer-moore search on char arrays

JavaX fragment (include)

sclass BoyerMoore_chars {
  final static int R = 256;     // the radix
  final int[] right;     // the bad-character skip array
  final char[] pat;      // pattern

  *(S pat) { this(toCharArray(pat)); }
  
  *(char[] *pat) {
    // position of rightmost occurrence of c in the pattern
    right = new int[R];
    for (int j = 0; j < pat.length; j++)
        right[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(char[] txt) {
    if (txt == null) ret -1;
    int m = pat.length;
    int n = txt.length;
    int skip;
    for (int i = 0; i <= n - m; i += skip) {
        skip = 0;
        for (int j = m-1; j >= 0; j--) {
            if (pat[j] != txt[i+j]) {
                skip = Math.max(1, j - (right[txt[i+j] & (R-1)]-1));
                break;
            }
        }
        if (skip == 0) ret i;
    }
    ret -1;
  }
}

Author comment

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