KMP
public class Solution {
public int[] getNext(String s){
int i = 0, j = -1;
int[] next = new int[s.length()];
next[0] = -1;
while(i < next.length - 1){
if(j == -1 || s.charAt(i) == s.charAt(j)){
i++; j++;
next[i] = j;
}else{
j = next[j];
}
}
return next;
}
public boolean KMP(String text, String word){
int[] next = getNext(word);
int i = 0, j = 0;
while(i < text.length() && j < word.length()){
if(j == -1 || text.charAt(i) == word.charAt(j)){
i++; j++;
}else {
j = next[j];
}
}
return (j == word.length()) ? true : false;
}
public static void main(String[] args) {
Solution solution = new Solution();
strA = "abaabaac";
strB = "abaac";
// KMP
System.out.println(solution.KMP(strA ,strB));
// java api ： 实现方式不是KMP
System.out.println(strA.indexOf(strB));
}
}
------------------------------------ Run (result)----------------------------------------
true
3
Process finished with exit code 0
