5.6 实现strStr() (串)——【LeetCode】

package com.string.java;

public class six {

	//方法一：
	//基于滑动窗口的算法
	public int strStr(String haystack, String needle) {
		int m = needle.length();
		// 当 needle 是空字符串时我们应当返回 0
		if(m == 0) {
			return 0;
		}
		int n = haystack.length();
		if(n < m) {
			return -1;
		}
		int i = 0;
		int j = 0;
		while(i < n - m + 1) {
			//找到首字母相等
			while(i < n && haystack.charAt(i) != needle.charAt(j)) {
				i++;
			}
			if(i == n) {//没有找到
				return -1;
			}
			//执行到此处，说明存在相等字符，继续遍历后续字符，判断是否相等
			i++;
			j++;
			while(i < n && j < m && haystack.charAt(i) == needle.charAt(j)) {
				i++;
				j++;
			}
			if(j == m) {//说明找到
				return i - j;//即i-m
			}else {//未找到 此处看到匹配不成功的话这里只是将needle向右移动了一下 重新匹配
				i -= j-1;
				j = 0;
			}
		}
		return -1;
	}

	//方法二：KMP
	public int strStr1(String haystack, String needle) {
		if(needle.length() == 0) {
			return 0;
		}
		int[] next = new int[needle.length()];
		getNext(next, needle);//获取needle的部分匹配值表
		
		for (int i = 0, j = 0; i < haystack.length(); i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) {
            	j = next[j - 1];//更新j值
            }
            if (needle.charAt(j) == haystack.charAt(i)) {
            	j++;
            }
            if (j == needle.length()) {
            	return i - needle.length() + 1;
            }
        }
		return -1;
	}
	
	//获取到一个字符串(子串) 的部分匹配值表
	private void getNext(int[] next, String dest) {

		next[0] = 0; //如果字符串是长度为1 部分匹配值就是0
		for(int i = 1,j = 0; i < dest.length();i++) {
			//当dest.charAt(i) != dest.charAt(j) ，我们需要从next[j-1]获取新的j
			//直到我们发现 有  dest.charAt(i) == dest.charAt(j)成立才退出
			//这是kmp算法的核心点
			while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
				j = next[j-1];
			}
			//当dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
			if(dest.charAt(i) == dest.charAt(j)) {
				j++;
			}
			next[i] = j;
		}
	}
}