28. Implement strStr().md

28. Implement strStr()

Question:

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Thinking:

• Method1: Iterate and compare

	class Solution {
	    public int strStr(String haystack, String needle) {
	        int len = needle.length();
	        int slen = haystack.length();
	        if(len == 0) return 0;
	        int i = 0;
	        while(i + len <= slen){
	            if(haystack.substring(i, i + len).equals(needle)){
	                return i;
	            }else{
	                i++;
	            }
	        }
	        return -1;
	    }
	}

二刷

二刷的时候已经研究了KMP算法，直接上KMP算法。 KMP算法讲解

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length() == 0) return 0;
        return kmp(haystack, needle);
    }
    private int[] getNext(String pattern){
		char[] arr = pattern.toCharArray();
		int len = pattern.length();
		int[] next = new int[len];
		next[0] = -1;
		for(int i = 1, j = -1; i < len; i++){
			while(j > -1 && arr[j + 1] != arr[i]){
				j = next[j];
			}
			if(arr[i] == arr[j + 1]) j++;
			next[i] = j;
		}
		return next;
	}
	public int kmp(String text, String pattern){
		int[] next = getNext(pattern);
		char[] tArr = text.toCharArray();
		char[] pArr = pattern.toCharArray();
		int tLen = text.length();
		int pLen = pattern.length();
		int j = -1;
		for(int i = 0; i < tLen; i++){
			while(j > -1 && tArr[i] != pArr[j + 1]){
				j = next[j];
			}
			if(tArr[i] == pArr[j + 1]) j++;
			if(j == pLen - 1) return i - pLen + 1;
		}
		return -1;
	}
}