kmp算法 java实现

在这就不介绍什么是kmp算法还有kmp算法的解决思路啦，具体算法概念跟解决思路请看此博客http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html 里面详细介绍了如何计算next数组，匹配的时候需要移动位数等规则。

在此只贴一下kmp算法的java实现：

public class kmp {

//获取next数组
public int[] getNextArray(String str){
char[] c = str.toCharArray();
int[] next = new int[c.length];
next[0] = 0 ;
int j = 1 ; //后序指针
int i = 0 ; //前序指针
while(j==0||j<c.length){
if(c[j]==c[i]){
next[j] = ++i;  
j++;
}else{
if(i==0){
j++;
}else{
i=0;
}
}
}
return next;
}

//匹配判断   
public boolean containt(String str,String checkStr){
char[] arrays = str.toCharArray();
char[] c = checkStr.toCharArray();
int[] next = getNextArray(checkStr);
int i = 0 ; 
int j = 0 ;
while(i<arrays.length){
if(arrays[i]==c[j]){
if(j==c.length-1){
return true;
}
i++;
j++;
}else{
if(j!=0){
j = next[j-1];   
}else{
i++;
}
}
}
return false ;
}

public static void main(String[] args) {
System.out.println(new kmp().containt("anansjjsajk","nans"));
}
}

时间复杂度O=m+n