28.实现strStr()

实现 strStr() 函数。

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

说明：

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

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

示例 1：

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

Solution

这字符串匹配肯定是KMP算法好，但是谁记得住啊？

写个bp算法得了

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
class Solution {
    public int strStr(String haystack, String needle) {
       // 将输入的字符串转换成字符数组，以便进行逐字符比较
       char [] a = haystack.toCharArray();
       char [] b = needle.toCharArray();
 
       // 外循环遍历haystack的每一个起始位置，直到达到最后一个可能匹配needle的起始位置
       for (int i = 0; i < a.length - b.length + 1; i++) {
            int j = 0; // 初始化needle的遍历指针
               // 内循环，当当前字符匹配时继续比较后续字符
               while(a[i] == b[j]){
                i++; // 移动haystack的指针
                j++; // 移动needle的指针
                // 如果needle的所有字符都成功匹配，返回当前匹配的起始位置
                if(j == b.length) {
                    return i - j; // i已经移动到匹配子串末尾的下一个位置，所以要减去needle的长度
                } 
               }
                // 如果当前位置的字符不匹配，回溯haystack的指针到本次匹配开始的下一个位置
                i = i - j;
       }
       // 如果整个循环完成后没有找到匹配的子串，返回-1
       return -1;
    }
}