输入：haystack = "hello", needle = "ll"输出：2来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/implement-strstr

public class DayCode {    public static void main(String[] args) {        String haystack = "hello", needle = "ll";
        int ans = new DayCode().strStr(haystack, needle);        System.out.println("ans is " + ans);
        int ans1 = new DayCode().strStr1(haystack, needle);        System.out.println("ans is " + ans1);
        int ans2 = new DayCode().strStr2(haystack, needle);        System.out.println("ans is " + ans2);    }
    /**     * 时间复杂度 O(m * n)     * 空间复杂度 O(1)     *     * @param haystack     * @param needle     * @return     */    public int strStr(String haystack, String needle) {        int n = haystack.length();        int m = needle.length();        for (int start = 0; start + m <= n; start++) {            if (haystack.substring(start, start + m).equals(needle)) {                return start;            }        }        return -1;    }
    /**     * 时间复杂度 O(m * n)     * 空间复杂度 O(1)     *     * @param haystack     * @param needle     * @return     */    public int strStr1(String haystack, String needle) {        int n = haystack.length();        int m = needle.length();        for (int i = 0; i + m <= n; i++) {            boolean flag = true;            for (int j = 0; j < m; j++) {                if (haystack.charAt(i + j) != needle.charAt(j)) {                    flag = false;                    break;                }            }            if (flag) {                return i;            }        }        return -1;    }
    /**     * 时间复杂度 O(m + n)     * 空间复杂度 O(1)     *     * @param haystack     * @param needle     * @return     */    public int strStr2(String haystack, String needle) {        int n = haystack.length();        int m = needle.length();        if (m == 0) {            return 0;        }
        int[] pi = new int[m];        for (int i = 1, j = 0; i < m; i++) {            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {                j = pi[j - 1];            }            if (needle.charAt(i) == needle.charAt(j)) {                j++;            }            pi[i] = j;        }
        for (int i = 0, j = 0; i < n; i++) {            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {                j = pi[j - 1];            }
            if (haystack.charAt(i) == needle.charAt(j)) {                j++;            }
            if (j == m) {                return i - m + 1;            }        }
        return -1;    }

}