QuickSearch.java

package ch.hslu.exercises.sw13.ex5;

import org.apache.commons.lang3.StringUtils;

public class QuickSearch {
    public static int quickSearch(final String searchString, final String pattern) {
        final int searchStringLength = searchString.length();
        final int patternLength = pattern.length();
        final int range = 256; // -> ASCII-Range
        final int[] shift = new int[range];
        // init shift-array
        for (int i = 0; i < range; i++) {
            shift[i] = patternLength + 1;
        }
        // overwrite fields according pattern
        for (int i = 0; i < patternLength; i++) {
            shift[pattern.charAt(i)] = patternLength - i;
        }

        String optimalPattern = pattern;


        // search
        int i = 0; // index to string
        int j = 0; // index to pattern
        do {
            if (searchString.charAt(i + pattern.indexOf(optimalPattern.charAt(j))) == optimalPattern.charAt(j)) { // match
                j++;
            } else { // mismatch
                if ((i + patternLength) < searchStringLength) { // searchString.charAt(i1+patternLength) is not outside searchString
                    optimalPattern = swap(optimalPattern, pattern.charAt(j));
                    i += shift[searchString.charAt(i + patternLength)]; // jump forward
                    j = 0;
                } else {
                    break; // (mismatch) && (no shift is possible)
                }
            }
        } while ((j < patternLength) && ((i + patternLength) <= searchStringLength));
        // (position at i not completely checked) && (end of searchString not reached)
        if (j == patternLength) {
            return i; // pattern found
        } else {
            return -1; // pattern not found
        }
    }

    private static String swap(String optimalPattern, char mismatchingChar) {
        int index = optimalPattern.indexOf(mismatchingChar);
        char[] optimalPatternCharArray = optimalPattern.toCharArray();
        if (index != 0) {
            char temp = optimalPatternCharArray[index - 1];
            optimalPatternCharArray[index - 1] = optimalPatternCharArray[index];
            optimalPatternCharArray[index] = temp;
        }

        return String.valueOf(optimalPatternCharArray);
    }
}