BoyerMoore

package patternMatching;


     // Liest zwei String ein - den Pattern und den zu durchsucheden Text
     //  sucht im Text nach dem Pattern indem es die
     //  bad-character rule des BoyerMoore Algorithmus verwendet
     //  (nicht bad-suffix-rule)


    public class BoyerMoore {
        private final int R;     // rechts
        private int[] right;     // das bad-character skip array

        private char[] pattern;  // pattern to charArray
        private String pat;      // or as a string

        // pattern als string
        public BoyerMoore(String pat) {
            this.R = 256;
            this.pat = pat;

            // rechteste position von C im 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;
        }

        // pattern als charArray
        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];

            // rechteste position von C im 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;
        }

        // return offset des ersten treffers, N falls kein treffer
        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
        }


        // return offset des ersten treffers, N falls kein treffer
        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
        }



        // test it!
        public static void main(String[] args) {
            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
            System.out.println("text:    " + txt);

            System.out.print("pattern: ");
            for (int i = 0; i < offset1; i++)
                System.out.print(" ");
            System.out.println(pat);

            System.out.print("pattern: ");
            for (int i = 0; i < offset2; i++)
                System.out.print(" ");
            System.out.println(pat);
        }
    }



    /*
    // je weiter hinten der mismatch, desto weite springt man
    // 3 fälle
    // wenn wir einen mismatch haben -> beweg dich i text soundso weiter
    // worstcase: immer nur um 1 springen! z.b. pattern = 1,


    public void runSearch(String text, String pattern) {
        int i = pattern.length(); //?? TODO
        int j = pattern.length();

        while (i <= text.length() && j > 0) {
            if (text.charAt(i-1) == pattern.charAt(j-1)) { // pattern ganz vorne
                i--; j--;
            } else { //TODO
                if ((s+1) > i + shifter.charAt(text.charAt(i))) {
                    i = s + 1;
                } else {
                    i = i + shifter();
                }
                if () {//TODO 3. schritt
                    //je weiter der abstand vom hinteren ende, desto weiter können wir vor gehen

                }
                i+= pattern.length();
                i+=abstand;
                i+=1;
            }
        }
    }
    */