NoobsDeSroobs

Bad char shift

Nov 6th, 2013
423
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.53 KB | None | 0 0
  1. package System;
  2.  
  3. import java.util.ArrayList;
  4.  
  5. public class Search {
  6.     private int[] bad_shift; //Jeg finner ikke et bedre navn. Koperte dette fra timen.
  7.     private final int CHAR_MAX = 256;
  8.  
  9.     public Search() {
  10.         bad_shift = new int[CHAR_MAX];
  11.     }
  12.  
  13.     public int[] find(char[] needle, char[] haystack){
  14.         ArrayList<Integer> list = new ArrayList<>();
  15.         if (needle.length>haystack.length) return null;
  16.         if (needle.length == 0) return new int[0];
  17.        
  18.         for (int i = 0; i < bad_shift.length; i++) {
  19.             bad_shift[i] = needle.length;
  20.         }
  21.        
  22.         int offset = 0, needleScan = 0;
  23.         int maxOffset = haystack.length - needle.length;
  24.         int end = needle.length-1;
  25.        
  26.         for (int i = 0; i < end; i++) {
  27.             bad_shift[(int)needle[i]] = end - i;
  28.         }
  29.        
  30.         while(offset < maxOffset){
  31.             //The needleScan start at the end and check backwards until it hits a mismatch. Since _ should allow any kind of symbol
  32.             //then we can simply skip once if we find this char in the current needle char.
  33.             for(needleScan = end; needle[needleScan] == haystack[needleScan+offset] || needle[needleScan] == '_'; needleScan--){
  34.                 if(needleScan == 0){ // this will count down for every match until 0. Then we have found the needle.
  35.                     list.add(new Integer(offset));
  36.                     break;
  37.                 }
  38.             }
  39.             offset += bad_shift[haystack[offset + end]];
  40.         }
  41.        
  42.         Integer[] temp = list.toArray(new Integer[list.size()]);
  43.         int[] results = new int[temp.length];
  44.         for (int i = 0; i < results.length; i++) {
  45.             results[i] = temp[i].intValue();
  46.         }
  47.         return results;
  48.     }
  49. }
Advertisement
Add Comment
Please, Sign In to add comment