Skip to content

LeetCode 28 实现 strStr()#

目录#

1. 题目描述#

1.1. Limit#

Time Limit: 2000 ms

Memory Limit: 131072 kB

1.2. Problem Description#

实现 strStr() 函数。

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

1.3. Sample Input 1#

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

1.4. Sample Output 1#

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

1.5. Notes#

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

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

1.7. Source#

LeetCode 28 实现 strStr()

2. 解读#

KMP算法

3. 代码#

const int MAXN = 1e5 + 1;

int Next[MAXN] = { 0 };

class Solution {

public:
    int getNext(string p, int length)
    {
        // 预计算Next，用于在失配的情况下得到j回溯的位置
        Next[0] = 0;
        Next[1] = 0;
        for (int i = 1; i < length; i++) {
            int j = Next[i];
            while (j && p[i] != p[j]) {
                j = Next[j];
            }
            Next[i + 1] = (p[i] == p[j]) ? j + 1 : Next[j + 1];
        }
        return 0;
    }

    // 在str中找pattern
    int kmp(string str, string pattern)
    {
        size_t slen = str.size();
        size_t plen = pattern.size();
        // 预计算Next[]数组
        getNext(pattern, plen);
        size_t j = 0;
        // 匹配str和pattern的每个字符
        for (size_t i = 0; i < slen; i++) {
            // 失配了，用Next[]找j的回溯位置
            while (j && str[i] != pattern[j]) {
                j = Next[j];
            }
            // 当前位置的字符匹配，继续
            if (str[i] == pattern[j]) {
                j++;
            }
            // 完全匹配
            if (j == plen && plen > 0) {
                // 匹配的起点是 i + 1 - plen，末尾是i
                //printf("at location = %lu, %c\n", i + 1 - plen, str[i + 1 - plen]);
                return i + 1 - plen;
            }
        }

        if(plen > 0){
            return -1;
        }else{
            return 0;
        }

    }
    int strStr(string haystack, string needle) {
        return kmp(haystack, needle);
    }
};

联系邮箱：curren_wong@163.com

CSDN：https://me.csdn.net/qq_41729780

知乎：https://zhuanlan.zhihu.com/c_1225417532351741952

公众号：复杂网络与机器学习

欢迎关注/转载，有问题欢迎通过邮箱交流。

二维码

Back to top