【4.20】LeetCode每日一题· 实现 strStr()

2021年04月20日 9时39分

标签： LeetCode 字符串 KMP

## 题目描述
实现[strStr()](https://baike.baidu.com/item/strstr/811469)函数。

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

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

对于本题而言，当`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 * 10^4
haystack 和 needle 仅由小写英文字符组成
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/implement-strstr "题目链接")

## 解题思路
一道**KPM算法**的板子题，详情请见[官方题解](https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/)，说的比较清楚。

### ⚠️ ⚠️ ⚠️ ⚠️注意：
* **由于在循环过程中，`getNext`函数中的变量`t`，或者主函数中的变量`j`在首元素即失配时会置为`-1`，而`string`的`length()`方法返回的是一个`unsigned long long (size_t)`类型的数，两者直接相比较会导致`-1`被强转成`size_t`也就是`2^64-1`一定是大于`s.length()`的导致出现问题。**
* ** 因此，建议直接开两个`int`类型的变量保存字符串长度，或者在`while`循环的判断条件中将字符串长度强转为`int`类型**。
## 代码
```cpp
class Solution {
public:
    int* getNext(string& s){
        const int len = s.length();
        int* next = new int[len];
        int t = next[0] = -1;
        int j = 0;
        while(j < len-1){
            if(t < 0 || s[j] == s[t]){
                j++; t++;
                next[j] = t;
            }else{
                t = next[t];
            }
        }
        return next;
    }

int strStr(string haystack, string needle) {
        if(needle.length() == 0) return 0;
        int* next = getNext(needle);
        int m = haystack.length(), n = needle.length();
        int i = 0, j = 0;
        while(i < m && j < n){
            if(j < 0 || haystack[i] == needle[j]){
                i++; j++;
            }else{
                j = next[j];
            }
        }
        if(j != needle.length()) return -1;
        return i - j;
    }
};
```

## 用时和内存
> 执行用时：0 ms，在所有 C++提交中击败了100.00%的用户
> 内存消耗：7 MB，在所有 C++提交中击败了12.99%的用户 </tex>
                            </div>
                        </div>
                    </div>
                    
                    <hr>
                    <div class="row mt-5">
                        <div class="col comment">
                            <h3>所有评论</h3>
                            <h5>暂无评论</h5>
                        </div>
                    </div>
                    
                    <div class="row mt-5">
                        <div class="col">
                            <h3> 新增评论 </h3> 
                            <form action="/comment/72/cmt-pst" method="post">
                                <input type="hidden" name="csrfmiddlewaretoken" value="7xLkkKVvmULV9zmyqlS6lPvvNf0aQ5OnVCVyDuYMUM9dIMmIUwk7lraT5aKxVFtb">
                                <div class="row">
                                    <div class="col mb-3">
                                        <label for="post-comment-body" class="form-label">评论</label>
                                        <textarea class="form-control" id="post-comment-body" name="comment-body" rows="5" placeholder="请输入评论">

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.20】LeetCode每日一题· 实现 strStr()