KMP经典实现public final class KMP 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 int[] next;public KMP(String s,String t){source = s.toCharArray();target = t.toCharArray();sourceLength = source.length;targetLength = target.length;next=new int[targetLength]; next[0] = -1;for (int i = 0, j = -1; i < targetLength - 1;) {if (j == -1 || target[i] == target[j]) {if (target[++i] != target[++j]) {next[i] = j;} else {next[i] = next[j];}} else {j = next[j];}}}@Overridepublic Iterator<Integer> iterator() {return this;}@Overridepublic boolean hasNext() {return fromIndex < sourceLength;}@Overridepublic Integer next() {int j = 0;while (j < targetLength && fromIndex < sourceLength) {if (j == -1 || target[j] == source[fromIndex]) {j++;fromIndex++;} else {j = next[j];}}if (j >= targetLength)return fromIndex - targetLength;elsereturn -1;}@Overridepublic void remove() {throw new UnsupportedOperationException();}public static void main(String[] args) {String dest = "1.2.3.4.5.6.7.8.9.0";KMP kmp = new KMP(dest, ".");while(kmp.hasNext()){System.out.println(kmp.next());}}}
