KMP的next数组,模板

KMP getNext()

public static int[] getNext(String pattern){
		int len = pattern.length();
		int[] next = new int[len];
		next[0] = -1;//初始化
		int index = 0;//当前位的下标
		int cur = -1;//前位的next,即next[0]
		while(index < len-1){//求解完所有的next
			if(cur == -1 || pattern.charAt(index) == pattern.charAt(cur)){//比较当前位与当前位的next所指的字符是否相等
				index++;
				cur++;//相等的话当前位的next+1作为下一位的next
				next[index] = cur;
			}
			else{
				cur = next[cur];//不相等,则找到当前位的next的next与当前位比较
			}
		}
		return next;
	}

 

全部评论

相关推荐

头像
不愿透露姓名的神秘牛友
06-06 21:28
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务