改进BM经典算法public final class BM implements Iterable<Integer>,Iterator<Integer>{private final char[] source;private final char[] target;private final int sourceLength;private final int targetLength;private int fromIndex = 0;private final HashMap<Integer,ArrayList<Integer>> info;public BM(String s,String t){this.source = s.toCharArray();this.target = t.toCharArray();this.sourceLength = this.source.length;this.targetLength = this.target.length;HashMap<Integer,ArrayList<Integer>> info = new HashMap<Integer, ArrayList<Integer>>();for(int i = 0; i < this.targetLength;i++){Integer integer = Integer.valueOf(this.target[i]);if(!info.containsKey(integer)){info.put(integer, new ArrayList<Integer>());}info.get(integer).add(i);}this.info = info;}@Overridepublic Iterator<Integer> iterator() {return this;}@Overridepublic boolean hasNext() {return this.fromIndex < this.sourceLength;}@Overridepublic Integer next() {for(;this.fromIndex < this.sourceLength;){int temp = this.source[fromIndex];ArrayList<Integer> list = this.info.get(temp);if (list != null) {for (int integer : list) {int index = find(this.fromIndex, integer);if (index != -1) {this.fromIndex = index + this.targetLength;return index;}}}this.fromIndex += this.targetLength;}return -1;}private int find(int s, int t){int i = s,j = t;for(;j >= 0 && i >=0;i--,j--){if(this.source[i] != this.target[j]){return -1;}}for(i = s + 1,j = t + 1;i < this.sourceLength && j < this.targetLength;j++,i++){if(this.source[i] != this.target[j]){return -1;}}if(j >= this.targetLength)return s - t;return -1;}@Overridepublic void remove() {throw new UnsupportedOperationException();}}
