28. 找出字符串中第一个匹配项的下标

leetcode链接：
https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/

题目分析

方法一
暴力求解，双重循环。缺点：时间复杂度高

方法二
KMP算法

方案一

class Solution {
    public int strStr(String haystack, String needle) {
        // 方法一：暴力求解，双重循环。缺点：时间复杂度高
        boolean flag = false;
        for (int i = 0; i <= (haystack.length() - needle.length()); i++) {
            for (int j = 0; j < needle.length(); j++) {
                if (haystack.charAt(i + j) != needle.charAt(j) ) {
                    flag = false;
                    break;
                } else {
                    flag = true;
                }
            }
            if (flag) {
                return i;
            }
        }

        return -1;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了46.50% 的Java用户
内存消耗:39.2 MB,击败了93.43% 的Java用户

分析

时间复杂度：
O( n * m )

空间复杂度：
O( 1 )

官方题解 – KMP算法

相关参考：

本地KMP算法参考

远程KMP算法参考

代码随想录：
https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#_28-%E5%AE%9E%E7%8E%B0-strstr

class Solution {
    public int strStr(String haystack, String needle) {
        int[] countNext = countNext(needle);
        int j = 0;

        for (int i = 0; i < haystack.length(); i++) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                if (j == (needle.length() - 1)) {
                    return i - j;
                }
                j++;
            } else {
                while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                    j = countNext[--j];
                }

                if (haystack.charAt(i) == needle.charAt(j)) {
                    j++;
                }
            }
        }
        return -1;
    }

    private int[] countNext(String needle) {
        int[] result = new int[needle.length()];

        int i = 1, j = 0;

        for (; i < needle.length(); i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = result[--j];
            }

            if (needle.charAt(i) == needle.charAt(j)) {
                result[i] = ++j;
            }
        }

        return result;
    }
}