publicclassKMP {
staticint[] next; /**
*
* @param t 模式串，求得模式串回溯的next函数
*/
staticvoidnext(String t) {
next = newint[t.length()];
next[0] = -1;
intj = -1;
inti = 0;
while(i < t.length()-1) {
if(j == -1|| t.charAt(i) == t.charAt(j)) {
i++;
j++;
if(t.charAt(i) == t.charAt(j)){
next = next[j];
}else{
next = j;
}
}else{
j = next[j];
}
} }
/** *
* @param s 主串
* @param t 模式串
* @param pos 从主串的pos下标位置开始匹配
*/
staticintmatch(String s,String t,intpos){
inti=pos;
intj=0;
while(i<s.length()&& j<t.length()){
if(j==-1|| s.charAt(i)==t.charAt(j)){
i++;
j++;
}else{
j = next[j];
}
}
if(j>t.length()-1){
returni-j;
}else{
return-1;
} }
publicstaticvoidmain(String[] args) {
String s = "aaaasad";
String t = "sa";
next(t);
System.out.println(match(s,t,0));
}}
