LeetCode-28-实现 strStr()

题目

来源：LeetCode.

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

说明：
当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：

输入：haystack = "hello", needle = "ll"
输出：2

示例 2：

输入：haystack = "aaaaa", needle = "bba"
输出：-1

示例 3：

输入：haystack = "", needle = ""
输出：0

提示：
$0<=haystack.length,needle.length<=5\ast 104$
$haystack$ 和 $needle$ 仅由小写英文字符组成

接下来看一下解题思路：

思路一：暴力匹配：

    可以让字符串 $\text{needle}$ 与字符串 $\text{haystack}$ 的所有长度为 $m$ 的子串匹配一次。。
    为了减少不必要的匹配，每次匹配失败立即停止当前子串的匹配，对下一个子串继续匹配。如果匹配成功，返回当前子串的开始位置，如果所有的子串都匹配失败，返回 $-1$

public int strStr(String haystack, String needle) {
    int n = haystack.length();
    int m = needle.length();
    if(m < 1) {
        return 0;
    }

    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(n\times m)$，其中 $n$ 是字符串 $\text{haystack}$ 的长度，$m$ 是字符串 $\text{needle}$ 的长度。
    空间复杂度：$O(1)$，只需要常数的空间保存若干变量。

思路二：KMP算法：

本题是经典的字符串单模匹配的模型，因此可以使用字符串匹配算法解决。
KMP算法的实现参考： KMP.

public int strStr(String haystack, String needle) {
    int h = haystack.length();
    int n = needle.length();

    if (n < 1) {
        return 0;
    }
    int[] next = getNext(needle);

    int i = 0;
    int j = 0;

    while (i < h && j < n) {
        if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    if (j == n) {
        return i - j;
    } else {
        return -1;
    }
}
public int[] getNext(String p) {
    int n = p.length();
    int[] next = new int[n];
    next[0] = -1;

    int j = 0;
    int k = -1;

    while (j < n - 1) {
        if (k == -1 || p.charAt(j) == p.charAt(k)) {
            if (p.charAt(++j) == p.charAt(++k)) {
                next[j] = next[k];
            } else {
                next[j] = k;
            }
        } else {
            k = next[k];
        }
    }
    return next;
}