public class KMP {
private char[] source = {'a','b','c','b','c','a','b','a','b','d','d','e','f','g','h','i','j','a','b','c','a','b','a','b','d','a'
};
private char[] target = {'a','b','c','a','b','a','b','d'
};
private int[] getNextArray(
char[] target){
int[] ret =
new int[target.length];
ret[0] = 0
;
for (
int i = 1; i < target.length; i++
) {
int offset = ret[i-1
];
while (offset > 0
) {
if (target[i] ==
target[offset]) {
ret[i] = offset + 1
;
break;
} else {
offset =
ret[offset];
}
}
if (offset == 0 && target[i] == target[0
]) {
ret[i] = 1
;
}
}
return ret;
}
private int indexOf(
int[] next) {
int offset = 0
;
int i = 0
;
while (i < target.length && offset <
source.length) {
if (target[i] ==
source[offset]) {
i++
;
offset++
;
} else if (i == 0
) {
offset++
;
} else {
i = i - 1 < 0 ? 0 : next[i - 1
];
}
}
return offset;
}
public static void main(String[] args) {
KMP k =
new KMP();
long now =
System.currentTimeMillis();
for (
int i = 0 ; i < 1000000 ; i++
) {
int[] ret =
k.getNextArray(k.target);
k.indexOf(ret);
}
System.out.println(System.currentTimeMillis() -
now);
}
}
转载于:https://www.cnblogs.com/guangshan/p/4898588.html
相关资源：JAVA上百实例源码以及开源项目
