View Javadoc
1   package ch.hslu.exercises.sw13.ex5;
2   
3   import org.apache.commons.lang3.StringUtils;
4   
5   public class QuickSearch {
6       public static int quickSearch(final String searchString, final String pattern) {
7           final int searchStringLength = searchString.length();
8           final int patternLength = pattern.length();
9           final int range = 256; // -> ASCII-Range
10          final int[] shift = new int[range];
11          // init shift-array
12          for (int i = 0; i < range; i++) {
13              shift[i] = patternLength + 1;
14          }
15          // overwrite fields according pattern
16          for (int i = 0; i < patternLength; i++) {
17              shift[pattern.charAt(i)] = patternLength - i;
18          }
19  
20          String optimalPattern = pattern;
21  
22  
23          // search
24          int i = 0; // index to string
25          int j = 0; // index to pattern
26          do {
27              if (searchString.charAt(i + pattern.indexOf(optimalPattern.charAt(j))) == optimalPattern.charAt(j)) { // match
28                  j++;
29              } else { // mismatch
30                  if ((i + patternLength) < searchStringLength) { // searchString.charAt(i1+patternLength) is not outside searchString
31                      optimalPattern = swap(optimalPattern, pattern.charAt(j));
32                      i += shift[searchString.charAt(i + patternLength)]; // jump forward
33                      j = 0;
34                  } else {
35                      break; // (mismatch) && (no shift is possible)
36                  }
37              }
38          } while ((j < patternLength) && ((i + patternLength) <= searchStringLength));
39          // (position at i not completely checked) && (end of searchString not reached)
40          if (j == patternLength) {
41              return i; // pattern found
42          } else {
43              return -1; // pattern not found
44          }
45      }
46  
47      private static String swap(String optimalPattern, char mismatchingChar) {
48          int index = optimalPattern.indexOf(mismatchingChar);
49          char[] optimalPatternCharArray = optimalPattern.toCharArray();
50          if (index != 0) {
51              char temp = optimalPatternCharArray[index - 1];
52              optimalPatternCharArray[index - 1] = optimalPatternCharArray[index];
53              optimalPatternCharArray[index] = temp;
54          }
55  
56          return String.valueOf(optimalPatternCharArray);
57      }
58  }
59