!7 /** * Takes a pattern string and an input string as command-line arguments; * searches for the pattern string in the text string; and prints * the first occurrence of the pattern string in the text string. * * @param args the command-line arguments */ public static void main(S[] args) { tt(); if (empty(args)) args = new S[] {"abc", "bcabc"}; String pat = args[0]; String txt = args[1]; char[] pattern = pat.toCharArray(); char[] text = txt.toCharArray(); BoyerMoore boyermoore1 = new BoyerMoore(pat); BoyerMoore boyermoore2 = new BoyerMoore(pattern, 256); int offset1 = boyermoore1.search(txt); int offset2 = boyermoore2.search(text); // print results println("text: " + txt); printNoNewLine("pattern: "); for (int i = 0; i < offset1; i++) printNoNewLine(" "); println(pat); printNoNewLine("pattern: "); for (int i = 0; i < offset2; i++) printNoNewLine(" "); println(pat); } /** * The {@code BoyerMoore} class finds the first occurrence of a pattern string * in a text string. *
* This implementation uses the Boyer-Moore algorithm (with the bad-character * rule, but not the strong good suffix rule). *
* For additional documentation, * see Section 5.3 of * Algorithms, 4th Edition 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 BoyerMoore { final int R; // the radix int[] right; // the bad-character skip array char[] pattern; // store the pattern as a character array S pat; // or as a string *(S pat) { this.R = 256; this.pat = pat; // position of rightmost occurrence of c in the pattern right = new int[R]; for (int c = 0; c < R; c++) right[c] = -1; for (int j = 0; j < pat.length(); j++) right[pat.charAt(j)] = j; } /** * Preprocesses the pattern string. * * @param pattern the pattern string * @param R the alphabet size */ public BoyerMoore(char[] pattern, int R) { this.R = R; this.pattern = new char[pattern.length]; for (int j = 0; j < pattern.length; j++) this.pattern[j] = pattern[j]; // position of rightmost occurrence of c in the pattern right = new int[R]; for (int c = 0; c < R; c++) right[c] = -1; for (int j = 0; j < pattern.length; j++) right[pattern[j]] = j; } /** * 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; n if no such match */ public int search(String txt) { 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.charAt(j) != txt.charAt(i+j)) { skip = Math.max(1, j - right[txt.charAt(i+j)]); break; } } if (skip == 0) return i; // found } return n; // not found } /** * Returns the index of the first occurrrence of the pattern string * in the text string. * * @param text the text string * @return the index of the first occurrence of the pattern string * in the text string; n if no such match */ public int search(char[] text) { int m = pattern.length; int n = text.length; int skip; for (int i = 0; i <= n - m; i += skip) { skip = 0; for (int j = m-1; j >= 0; j--) { if (pattern[j] != text[i+j]) { skip = Math.max(1, j - right[text[i+j]]); break; } } if (skip == 0) return i; // found } return n; // not found } }