#28实现strStr_查找子字符串

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-strstr
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 暴力思路:
  称haystack为主串,needle为子串
  利用指针 i , j 和辅助指针 k ,指针 i 用于记录主串开始查找的角标, 指针 j 用于 记录 查找匹配的角标 , 辅助指针 k 用于 每个字符匹配成功,依次往后移动.

  一:外循环的循环条件为 haystack.length() - needle.length() + 1,因为防止角标溢出,
  循环条件为什么要加1 ,比如 needle参数 是 aa ,那么他的长度为2,但角标只有0和1,那么减去2之后,就减多了1,就加回1,可以通过一个简单的事例推一下这个循环条件

  二:中间逻辑条件: 如果字符不相等,直接break内循环,开始下一个外循环,如果字符相等,那么辅助指针就k++,开始下一个字串的配对

  三:如何判断匹配完成? : 在内循环中,如果没有被break,则证明已经完全遍历了一遍needle ,那么 判断 j 是否到达了needle的末尾,如果到了末尾则返回成功匹配字符串开始的角标 i

public static int strStr(String haystack, String needle) {
        if (needle.equals(""))
            return 0;
        // 循环条件为什么要加1 ,比如 needle参数 是 aa ,那么他的长度为2,但角标只有0和1,那么减去2之后,就减多了1,就加回1,可以通过一个简单的事例推一下这个循环条件
        for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
            int k = i;
            int j = 0;
            for (; j < needle.length(); j++) {
                if (haystack.charAt(k) != needle.charAt(j)) {
                    break;
                }
                k++;
            }
            // 在上面的for循环中,如果没有被break,则证明已经完全遍历了一遍needle ,那么 判断 j 是否到达了needle的末尾,如果到了末尾则返回成功匹配字符串开始的角标 i
            if (j == needle.length())
                return i;
        }
        return -1;
    }

• kmp思路:
  称haystack为主串,needle为子串
  用两个指针 i 和 j 来记录 主串和子串的角标
  一:从左往右一个一个字符匹配
  二:如果字符相等,则开始下一个字符匹配 i++ j++
  三:否则指针 i 回退到 刚开始匹配的角标的后一位, 即 i - j + 1 ,子串角标归零 j = 0;
  四:while循环结束后,则证明主串或者子串有一方已经到达了末尾,那么就判断子串角 标 j 是否等于子串的末尾,即j == 子串.length,如果到达了末尾,即完成了匹配,返回刚开始匹配的第一个角标的位置,即 i - j

    //created by Fivezm on 2019.7.19  kmp解法
    public static int strStr(String haystack, String needle) {

        char[] haystackArr = haystack.toCharArray();
        char[] needleArr = needle.toCharArray();
        // 两个指针,一个记录主串,一个记录子串
        int i = 0;
        int j = 0;
        //当指针都不超出彼此的字符串长度时循环
        while (i < haystackArr.length && j < needleArr.length) {
            //如果 这两个字符相等,那么匹对下一个字符是否相等
            if (haystackArr[i] == needleArr[j]) {
                i++;
                j++;
            } else { // 如果字符不相等,i 回退到 原本的位置后一位的下标 , j 归零
                i = i - j + 1;
                j = 0;
            }
        }
        // 如果 j 角标到达了 子串末尾,则证明匹配匹配成功,返回 主串中 i 开始角标的位置
        if (j == needleArr.length)
            return i - j;
        return -1;
    }