实现 strStr()，给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。_利用strstr输出对应下标

题记：
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：
输入：haystack = “sadbutsad”, needle = “sad”
输出：0
解释：“sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：
输入：haystack = “leetcode”, needle = “leeto”
输出：-1
解释：“leeto” 没有在 “leetcode” 中出现，所以返回 -1 。

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

题目来源：
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnr003/
来源：力扣（LeetCode）

自己想出来的方法：
方法一：循环遍历，挨个做匹配比较（效率低）

class Solution {

    /**
     * @param String $haystack
     * @param String $needle
     * @return Integer
     */
    function strStr($haystack, $needle) {
		        if(strlen($haystack) == 0 || strlen($needle) == 0){
            return -1;
        }
        if($haystack == $needle){
            return 0;
        }

        //拆分为数组
        $haystack_array = str_split($haystack);
        $needle_array = str_split($needle);
        $haystack_length = count($haystack_array);
        $needle_length = count($needle_array);
        $find = [[]];
        $index_array = [];

        for($i = 0; $i < $haystack_length; $i++){
            //找到需要查询的子字符串第一个字符在母字符串中出现的位置
            if($haystack_array[$i] == $needle_array[0]){
                array_push($index_array,$i);
            }

        }

        //遍历字符串首字符在母字符串出现的位置的数组
        foreach($index_array as $k => $v){
            foreach($haystack_array as $key => $value){
                //标记出现的初始位置以及应该结束查找的位置
                if($v == $key  && ($key + $needle_length) <= $haystack_length){
                    $end_index = $key + $needle_length;
                    $start_index = $v;
                }

                //将截取到的数据插入数组
                if(isset($start_index) && isset($end_index) && $start_index < $end_index && $end_index <= $haystack_length){
                    while($start_index < $end_index){
                        $find[$v][] = $haystack_array[$start_index];
                        $start_index++;
                    }
                }
            }
        }

        //循环遍历做比较，是否相等
        foreach($find as $key => $value){
            if($value == $needle_array){
                return $key;
            }
        }

        return -1;
    }
}
$haystack = "abc";
$needle = "c";
$solution = new Solution();
$result = $solution->strStr($haystack,$needle);
var_dump($result);
/**
输出结果为：int(2)
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

方法二：使用内置函数

class Solution {

    /**
     * @param String $haystack
     * @param String $needle
     * @return Integer
     */
    function strStr($haystack, $needle) {
        $pos = strpos($haystack,$needle);	//strpos — 查找字符串首次出现的位置
        if($pos !== false){
            return $pos;
        }
        return -1;
    }
}
$haystack = "abc";
$needle = "c";
$solution = new Solution();
$result = $solution->strStr($haystack,$needle);
var_dump($result);
/**
输出结果为：int(2)
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法三：截取字符比较

class Solution {

    /**
     * @param String $haystack
     * @param String $needle
     * @return Integer
     */
    function strStr($haystack, $needle) {
        $haystack_length = strlen($haystack);
        $needle_length = strlen($needle);
        if($haystack_length == 0 || $needle_length== 0){
            return -1;
        }
        if($haystack == $needle){
            return 0;
        }

        $haystack_array = str_split($haystack); //拆分为数组
        $needle_array = substr($needle,0,1);    //找到子字符串的首字符

        $index_array = [];
        for($i = 0; $i < $haystack_length; $i++){
            //找到需要查询的子字符串第一个字符在母字符串中出现的位置
            if($haystack_array[$i] == $needle_array[0]){
                array_push($index_array,$i);
            }

        }

        foreach($index_array as $key => $v){
            if(($v + $needle_length) <= $haystack_length){
                if(substr($haystack,$v,$needle_length) == $needle){
                    return $v;
                }
            }
            
        }
        return -1;
    }
}
$haystack = "abc";
$needle = "c";
$solution = new Solution();
$result = $solution->strStr($haystack,$needle);
var_dump($result);
/**
输出结果为：int(2)
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

官方答案：
一：一行代码搞定

    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
1
2
3

二：逐个判断（效率较差）

一般字符串匹配的时候，最简单的一种方式，就是子串从头开始和主串匹配。

如果匹配失败，子串再次从头开始，而主串从上次匹配的下一个字符开始，代码如下

    public int strStr(String haystack, String needle) {
        if (needle.length() == 0)
            return 0;
        int i = 0;
        int j = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                //如果不匹配，就回退，从第一次匹配的下一个开始，
                i = i - j + 1;
                j = 0;
            }
            if (j == needle.length())
                return i - j;
        }
        return -1;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三：不断截取主串然后再比较

    public int strStr(String haystack, String needle) {
        int length = needle.length();
        int total = haystack.length() - length + 1;
        for (int start = 0; start < total; ++start) {
            if (haystack.substring(start, start + length).equals(needle)) {
                return start;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10

四：KMP算法（有待了解）

其实这题是一道典型的KMP算法题，KMP算法的本质就是减少重复计算，我们举个例子，比如下面的图中，在最后一步比较失败的时候，然后子串又要从头开始，主串要从上一次比较的下一个字符开始，实际上前面的一些比较成功的数据我们是可以利用的。如下图所示，如果匹配失败的话，下一步主串还从失败的地方比较就可以了。

来看下代码

    public int strStr(String haystack, String needle) {
        if (needle.length() == 0)
            return 0;
        int i = 0;
        int j = 0;
        /**
         * 数组next表示pattern指定的下标前具有相同的字符串数量，语言组织能力不好，可能不是太好理解，我举个例子吧
         * ，比如ABCABA，数组next[0]是-1，这个是固定的，因为第一个A前面是没有字符的，next[1]是0，因为B的前面就一个A，没有
         * 重复的，所以是0,同理next[2]也是,next[3]也是0,而next[4]是1，因为next[4]所指向的是第二个B，第二个B前面有一个A和
         * 第一个A相同，所以是1,next[5]是2，因为next[5]所指向的是最后一个Ａ，因为前面的Ａ对比成功，并且Ｂ也对比成功，所以是２，
         * 也就是ＡＢ两个字符串匹配成功,再举个例子，比如WABCABA，数组除了第一个为-1，其他的都是为0，因为只有第一个匹配成功之后
         * 才能匹配后面的，虽然后面的AB和前面的AB匹配成功，但是后面AB的前面是C和前面AB的前面一个W不匹配，所以后面的匹配都是0.
         * 要记住只有指定字符前面的字符和第一个字符匹配成功的时候才能往后匹配，否则后面的永远都是先和第一个匹配。
         */
        int[] next = new int[needle.length()];
        getNext(needle, next);
        while (i < haystack.length() && j < needle.length()) {
            /**
             * 这里j等于-1的时候也只有在下面next数组赋值的时候才会出现，并且只有在数组next[0]的时候才会等于-1，
             其他时候是没有的，这一点要谨记，待会下面求next数组的时候就会用到。这里可以这样来理解，如果j不等于-1，
             并且下标i和j所指向的字符相等，那么i和j分别往后移一位继续比较，这个很好理解，那么如果j==-1的时候，就表示
             就表示前面没有匹配成功的，同时i往后移一位，j置为0（j==-1的时候，j++为0），再从0开始比较。
             */
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                /**
                 * i = i - j + 1;
                 j = 0;
                 返回到指定的位置，不是返回到匹配失败的下一个位置，这里都好理解，重点是求数组next。
                 这里只要j等于0，在next[j]赋值的之后，j就会等于-1；因为next[0]等于-1
                 */
                j = next[j]; // j回到指定位置
            }
            if (j == needle.length())
                return i - j;
        }
        return -1;
    }

    private void getNext(String p, int next[]) {
        int len = p.length();
        int i = 0;
        int j = -1;
        next[0] = -1;//这个默认的，
        /**
         * 匹配的时候是当前字符的前一个和前面的匹配，所以最后一个是不参与匹配的，可以看strStr方法的注释，
         */
        while (i < len - 1) {
            if (j == -1 || p.charAt(i) == p.charAt(j)) {
                /**
                 * 如果j不等于-1，指定的字符相等，那么i和j要往后移一位，这点很好理解，如果j为-1的时候，i往后移移位，j置为0
                 * 重新开始匹配。next[i]是匹配成功的数量
                 */
                i++;
                j++;
                next[i] = j;
            } else
            /**
             * 关键是这里不好理解，为什么匹配失败要让next[j]等于j，要记住这里的next[j]是指匹配成功的数量，有可能为0，也有可能是其他数.比如
             * 字符串ABCABXYABCABATDM,对应的next数组为{-1	0	0	0	1	2	0	0	1	2	3	4	5	1	0	0	}
             */
                j = next[j];
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

官方答案来源：
作者：数据结构和算法
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnr003/?discussion=fsbtRE
来源：力扣（LeetCode）