leetcode28. 实现 strStr()

1.题目描述：

实现strStr()函数。给你两个字符串haystack和needle，请你在haystack字符串中找出needle字符串出现的第一个位置（下标从0开始）。如果不存在，则返回-1。

2.KMP算法：就是实现String.indexOf(String str)，时间复杂度O(m + n)。

前缀表减一：

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack.length() < needle.length()) return -1;
        int[] next = getNext(needle);
        int j = -1;
        for (int i = 0; i < haystack.length(); i++) {
            while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
                j = next[j];
            }
            if (haystack.charAt(i) == needle.charAt(j + 1)) j++;
            if (j == needle.length() - 1) return i - needle.length() + 1; 
        }
        return -1; 
    }

    public int[] getNext(String s) {
        int[] next = new int[s.length()];
        int j = -1;
        next[0] = j;
        for (int i = 1; i < next.length; i++) {
            while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
                j = next[j];//有动态规划的思想
            }
            if (s.charAt(i) == s.charAt(j + 1)) j++;
            next[i] = j;
        }
        return next;
    }
}

前缀表不减一：（变化很小）

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack.length() < needle.length()) return -1;
        int[] next = getNext(needle);
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) j++;
            if (j == needle.length()) return i - needle.length() + 1; 
        }
        return -1; 
    }

    public int[] getNext(String s) {
        int[] next = new int[s.length()];
        int j = 0;
        next[0] = j;
        for (int i = 1; i < next.length; i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) j++;
            next[i] = j;
        }
        return next;
    }
}

 3.滑动窗口：时间复杂度O(m * n)。

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