KMP 算法 java实现

在网上找到的代码运行出来的模式值和资料里根据定义计算出来的值不一样， 没有找到合适的，于是手写了一个。

 

 

模式值定义：

（1）next[0]= -1  意义：任何串的第一个字符的模式值规定为-1。

（2）next[j]= -1   意义：模式串T中下标为j的字符，如果与首字符相同，且j的前面的1—k个字符与开头的1—k个字符不等（或者相等但T[k]==T[j]）（1≤k<j）。

    如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]

（3）next[j]=k    意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且T[j] != T[k] （1≤k<j）。

                       即T[0]T[1]T[2]。。。T[k-1]==T[j-k]T[j-k+1]T[j-k+2]…T[j-1]  且T[j] != T[k].（1≤k<j）;

（4）next[j]=0   意义：除（1）（2）（3）的其他情况。

 

 

 

取next 模式值的代码如下：

 

	/**
	 * 获取模式值数组
	 * @param str
	 * @return
	 */
	public int[] nextModel(String str){
		int[] arrays=new int[str.length()];
		for (int i = 0; i < arrays.length; i++) {
			arrays[i]=getNextModelVal(str, i);
		}
		return arrays;
	}
	
	/**
	 * 计算模式值
	 * @param index 索引值
	 * @return 当前索引位置的模式值
	 */
	private int getNextModelVal(String str,int index){
		
		char[] crs = str.toCharArray();
		
		if(index==0){
			return -1;
		}
		
		int result = 0;
		if(index>1){
			begin:
			for(int k=1;k<index;k++){
				//从头取k个值
				//从索引前取  
				int kindex=index-k;
				for(int count = 0 ;count <k ;count ++ ){
					if(crs[count] != crs[kindex+count]){
						continue begin;
					}
				}
				result=k;
				break;
			}
			if(result==0){
				//t[k]!=t[j]
				result=-1;
			}else{
				if(crs[result]==crs[index]){
					result=-1;
				}
			}
		}
		
		return result;
	}