实现strStr

力扣 28. 实现 strStr()

题目说明

实现 strStr() 函数。

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

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

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

示例

例1

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

例2

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

例3

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

笔者理解

此题是一道字符串算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题拥有多种解法，本文采用一种比较简单的匹配首字符方法，让我们来看看具体如何实现的吧。

实现

public int strStr(String haystack, String needle) {
        int haystackSize = haystack.length();
        int needleSize = needle.length();

        // 目标字符串为空或者两字符串相等
        if (needleSize == 0 || haystack.equals(needle)) {
            return 0;
        }

        // 目标字符串长于源字符串
        if (needleSize > haystackSize) {
            return -1;
        }

        // 取目标字符串首字符
        char first = needle.charAt(0);

        // 比较时的最大相对位移
        int max = haystackSize - needleSize;

        for (int i = 0; i <= max; i++) {
            if (haystack.charAt(i) != first) {
                // 向后移动直到匹配第一个字符为止
                while (++i <= max && haystack.charAt(i) != first);
            }

            if (i <= max) {
                int j = i + 1;
                int end = j + needleSize - 1;
                // 向后比较
                for (int k = 1; j < end && haystack.charAt(j)
                        == needle.charAt(k); j++, k++);

                // 相同长度等于目标字符串长度
                if (j == end) {
                    return i;
                }
            }
        }

        return -1;
    }