28-实现strStr()

LeetCode

发布日期: 2022-02-21

LeetCode 28. Implement strStr()

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

method: KMP

文本串：aabaabaaf
模式串：aabaaf

next数组记录最大的前后缀相等的长度，这样当某个元素不匹配的时候，就可以跳到最大相等前缀的位置重新匹配，而不用跳到开头

因为知道了这一串的某个后缀与前缀是相等的，所以就直接跳到相等前缀的位置开始匹配，节省时间

1、求next数组

前缀是包含首字符，不包含尾字符的所有子串，a, aa, aab, aaba, aabaa
后缀是包含尾字符，不包含首字符的所有子串，f, af, aaf, baaf, abaaf

aa的前缀是a，后缀是a，所以最长相等前后缀长度为1
aabaa有个是aa，有个后缀是aa，所以最长相等前后缀长度为2

定义两个指针i和j，j指向前缀末尾位置，刚开始前缀为空，所以j初始化为0，还表示i及i之前的子串的最长相等前后缀长度，所以后面next[i]=j
i指向后缀末尾位置，后缀要从后往前看，刚开始后缀为abaaf，所以i指向1的位置
s[j]!=s[i]时，j要根据前一个字符的next值回退，直至退到0
s[j]==s[i]时，j递增
i位置的next值就是j

2、文本串和模式串匹配

模式串: a a b a a f
next : 0 1 0 1 2 0

第一次到f时不匹配

文本串: a a b a a b a a f
模式串: a a b a a f
next : 0 1 0 1 2 0

f前面的a的next值为2，所以跳到2的位置重新匹配

文本串: a a b a a b a a f
模式串:       a a b a a f
next :       0 1 0 1 2 0

这样就匹配上了

vector<int> next;
void getNext(string s) {
    int j = 0;
    for (int i = 1; i < s.size(); i++) {
        while (j > 0 && s[j] != s[i]) { // 要用while
            j = next[j - 1];    // j要回退
        }
        if (s[j] == s[i]) j++;
        next[i] = j;
    }
}
int strStr(string haystack, string needle) {
    if (needle.size() == 0) return 0;
    next.resize(needle.size(), 0);
    getNext(needle);
    int j = 0;
    for (int i = 0; i < haystack.size(); i++) { // 遍历文本串
        while (j > 0 && needle[j] != haystack[i]) {
            j = next[j - 1];
        }
        if (needle[j] == haystack[i]) j++;
        if (j == needle.size()) return i - j + 1;   // j刚好是模式串的长度 [res,i] i - res + 1 = len = j
    }
    return -1;
}