|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 糖逗 于 2020-5-8 14:31 编辑
题目描述:
- 实现 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
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- class Solution {
- public:
- int strStr(string haystack, string needle) {
- if(!needle.size()) return 0;
- if(!haystack.size()) return -1;
- //先构造pattern
- int j = -1, i = 0;//j在后面,i在前面
- vector<int> b(needle.size() + 1);
- b[i] = j;
- while(i < needle.size()){
- while(j >= 0 && needle[i] != needle[j]) j = b[j];
- i++, j++;
- b[i] = j;
- }
- j = 0, i = 0; //j这回是text的, i是pattern的
- while(j < haystack.size()){
- while(i >= 0 && needle[i] != haystack[j]) i = b[i];
- i++, j++;
- if(i == needle.size()){
- return j - needle.size();
- }
- }
- return -1;
- }
- };
复制代码
KMP学习参考链接:https://www.bilibili.com/video/B ... 265636f5f6c697374.2 |
|