笔记1 记录JAVA 的KMP算法

public class KMP {

    //获取NEXT数组的函数
	public static int[] GetArrNext(String str){
		int[] Next= new int[str.length()];
		String TempStr;
		String TempStr1;
		String TempStr2;
		int Temp;
		for(int i=0;i 
NEXT数组的定义：
 
对于字符串P[0]-P[X]，NEXT[X]的值K恰好为满足P[0]~P[K]=P[X-K]~P[X]的最大值
 
优化求NEXT数组的过程:
 
已知NEXT[X]求NEXT[X+1]
 
令NOW = X
 
若P[X+1]=P[NEXT[NOW]] //P为单个字符
 
则NEXT[X+1]=NEXT[NOW]+1;       
 
若P[X+1]！=P[NEXT[NOW]]
 
 
令NOW = X-1
 
直到NEXT[NOW]=0
 
 
优化后
 
public static int[] GetArrNext2(String str){
		int[] Next= new int[str.length()+1];
		int i = 1,now = 0;
		
		while(i 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5079862.html