【Day 84 】2023-05-08 - 28 实现 strStr(

[azl397985856]

28 实现 strStr(

入选理由

暂无

题目地址

[ 之 KMP 篇）

https://leetcode-cn.com/problems/implement-strstr/]( 之 KMP 篇）

https://leetcode-cn.com/problems/implement-strstr/)

前置知识

• 滑动窗口
• 字符串
• Hash 运算

  题目描述

  
  实现 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() 定义相符。

[Diana21170648]

思路

KMP

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n=len(haystack)
        m=len(needle)
        if not needle:
            return 0
        if m>n:
            return -1
        def KMPnext(needle):
            next=[None]*len(needle)
            j=0
            for i in range(1,len(needle)):
                while needle[i] != needle[j]:
                    if j>0:
                        j=next[j-1]
                    else:
                        next[i]=0
                        break 
                if needle[i]==needle[j]:
                    j+=1
                    next[i]=j
            return next
        next=KMPnext(needle)
        i,j=0,0
        while i<n and j<m:
            if haystack[i]==needle[j]:
                i+=1
                j+=1
            else:
                if j>0:
                    j=next[j-1]
                else:
                    i+=1
            if j==m:
                return i-j
        return -1

**复杂度分析**
- 时间复杂度：O(N+M)，其中 N 为待匹配数组长度。
- 空间复杂度：O(N)

[jackgaoyuan]

func getNext(next []int, s string) {
    j := -1 // j表示 最长相等前后缀长度
    next[0] = j

    for i := 1; i < len(s); i++ {
        for j >= 0 && s[i] != s[j+1] {
            j = next[j] // 回退前一位
        }
        if s[i] == s[j+1] {
            j++
        }
        next[i] = j // next[i]是i（包括i）之前的最长相等前后缀长度
    }
}
func strStr(haystack string, needle string) int {
    if len(needle) == 0 {
        return 0
    }
    next := make([]int, len(needle))
    getNext(next, needle)
    j := -1 // 模式串的起始位置 next为-1 因此也为-1
    for i := 0; i < len(haystack); i++ {
        for j >= 0 && haystack[i] != needle[j+1] {
            j = next[j] // 寻找下一个匹配点
        }
        if haystack[i] == needle[j+1] {
            j++
        }
        if j == len(needle)-1 { // j指向了模式串的末尾
            return i - len(needle) + 1
        }
    }
    return -1
}

[zhangyu1131]

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size();
        int m = needle.size();
        vector<int> next = buildNextArray(needle);

        int i = 0, j = 0;
        while (i < n)
        {
            if (haystack[i] == needle[j])
            {
                if (j == m - 1) // 完全匹配
                {
                    return i - j;
                }
                i++;
                j++;
            }
            else
            {
                if (j > 0)
                {
                    j = next[j - 1];// 回溯
                }
                else
                {
                    i++;
                }
            }
        }

        return -1;
    }

private:
    vector<int> buildNextArray(const string& needle)
    {
        int n = needle.size();
        int i = 0, j = 1;// 构建next数组的前后两个idx
        vector<int> next(n, 0);
        while (j < n)
        {
            if (needle[i] == needle[j])
            {
                // 前后相同，有一个匹配的前缀和后缀
                next[j] = i + 1;
                i++;
                j++;
            }
            else
            {
                // 不匹配
                if (i > 0)
                {
                    i = next[i - 1];// 用“aabaaa”这个例子来感受这一行代码，最后一个a和第三个b相比较不相同，就把i向前移一位。意思就是最大相同长度2不行的时候，就回溯看看长度为1行不行
                }
                else
                {
                    next[j] = 0;
                    j++;
                }
            }
        }

        return next;
    }
};

[chanceyliu]

代码

function strStr(haystack: string, needle: string): number {
  const n = haystack.length;
  const m = needle.length;
  for (let i = 0; i + m <= n; i++) {
    let flag = true;
    for (let j = 0; j < m; j++) {
      if (haystack[i + j] != needle[j]) {
        flag = false;
        break;
      }
    }
    if (flag) {
      return i;
    }
  }
  return -1;
}

复杂度分析

• 时间复杂度：O(n * m)
• 空间复杂度：O(a)

[harperz24]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        h, n = len(haystack), len(needle)
        if h < n:
            return -1

        next = self.getNext(needle)
        i = 0
        j = 0
        while i < h and j < n:
            if j == -1 or haystack[i] == needle[j]:
                i += 1
                j += 1
            else:
                j = next[j]

        if j == n: # j走到了末尾，说明匹配到了
            return i - j
        else:
            return -1

    def getNext(self, word):
            next = [0] * (len(word) + 1)
            next [0] = -1
            i = 0
            j = -1
            while i < len(word):
                if j == -1 or word[i] == word[j]:
                    i += 1
                    j += 1
                    next[i] = j     
                else:
                    j = next[j]

            return next

[snmyj]

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }
        vector<int> next(m);
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) {
                j = next[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            next[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack[i] != needle[j]) {
                j =next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
};

[wangqianqian202301]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(needle) == 0:
            return 0
        haystackLen = len(haystack)
        needleLen = len(needle)
        if needleLen > haystackLen:
            return -1
        for i in range(haystackLen - needleLen + 1):
            begin = i
            for nc in needle:
                if haystack[begin] != nc:
                    break
                begin = begin + 1
            if (i + needleLen) == begin:
                return i
        return -1

[61hhh]

思路

双指针

代码

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() > haystack.length()) {
            return -1;
        }
        int l1 = 0;
        int l2 = 0;
        int index = -1;
        while (l1 < haystack.length() && l2 < needle.length()) {
            if (haystack.charAt(l1) == needle.charAt(l2)) {
                if (index == -1) {// index初次更新
                    index = l1;
                }
                if (l2 == needle.length() - 1) {// needle遍历完了
                    return index;
                }
                l2++;// needle只有匹配上才后移
            } else {
                if (index != -1) {// 没能完全匹配 重置
                    l1 = index;
                    l2 = 0;
                    index = -1;
                }
            }
            l1++;// haystack始终后移
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：O(N*M)
• 空间复杂度：O(1)

[lp1506947671]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        if not needle: return 0
        if m > n: return -1

        # 维护一个pattern的next数组
        def KMPNext(needle):
            next = [None] * len(needle)
            j = 0
            for i in range(1, len(needle)):
                while needle[i] != needle[j]:
                    if j > 0:
                        j = next[j - 1]
                    else:
                        next[i] = 0
                        break
                if needle[i] == needle[j]:
                    j += 1
                    next[i] = j
            return next

        next = KMPNext(needle)
        i, j = 0, 0

        while i < n and j < m:
            if haystack[i] == needle[j]:
                i += 1
                j += 1
            else:
                if j > 0:
                    j = next[j - 1]
                else:
                    i += 1
            if j == m:
                return i - j

        return -1

复杂度分析

设：待匹配串长为NN，模式串串长为MM

时间复杂度：

• BF：O(NM)
• RK：若 hash function 选的差，冲突多，则最坏是(NM)，一般情况是O(N+M)
• KMP：O(N+M)

空间复杂度：

• BF：O(1)
• RK：O(1)
• KMP：O(M)

[kangliqi1]

class Solution { public int strStr(String haystack, String needle) {

    if (needle.length() == 0)
        return 0;

    int i = 0, j = 0;

    int[] next = getNext(needle);

    while (i < haystack.length() && j < needle.length()) {

        if (haystack.charAt(i) == needle.charAt(j)) {

            i++;
            j++;
        } else {

            if (j > 0)
                j = next[j - 1];
            else
                i++;
        }

        if (j == needle.length())
            return i - j;
    }

    return -1;
}

public int[] getNext(String pattern) {

    int[] next = new int[pattern.length()];

    int j = 0;
    for (int i = 1; i < pattern.length(); i++) {

        if (pattern.charAt(i) == pattern.charAt(j))
            next[i] = ++j;
        else {

            while (j > 0 && pattern.charAt(j) != pattern.charAt(i))
                j = next[j - 1];

            if (pattern.charAt(i) == pattern.charAt(j))
                next[i] = ++j;
        }
    }

    return next;
}

}

[SoSo1105]

class Solution: def strStr(self, haystack: str, needle: str) -> int: h, n = len(haystack), len(needle) if h < n: return -1

    next = self.getNext(needle)
    i = 0
    j = 0
    while i < h and j < n:
        if j == -1 or haystack[i] == needle[j]:
            i += 1
            j += 1
        else:
            j = next[j]

    if j == n: # j走到了末尾，说明匹配到了
        return i - j
    else:
        return -1

def getNext(self, word):
        next = [0] * (len(word) + 1)
        next [0] = -1
        i = 0
        j = -1
        while i < len(word):
            if j == -1 or word[i] == word[j]:
                i += 1
                j += 1
                next[i] = j     
            else:
                j = next[j]

        return next

[Jetery]

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0)
            return 0;
        vector<int> next(m);
        next[0] = -1;
        int j = -1;
        for (int i = 1; i < m; i++) {
            while (j > -1 && needle[i] != needle[j + 1]) j = next[j];
            if (needle[i] == needle[j + 1]) j++;
            next[i] = j;
        }

        j = -1;
        for (int i = 0; i < n; i++) {
            while (j > -1 && haystack[i] != needle[j + 1]) j = next[j];
            if (haystack[i] == needle[j + 1]) j++;
            if (j == m - 1)
                return i - m + 1;
        }
        return -1;
    }
};

[FireHaoSky]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        MOD = 10**9+7   # 模底
        base = 31       # 进制

        '''字符编码'''
        def encode(ch):
            return ord(ch) - ord('a') + 1

        n, m = len(haystack), len(needle)
        if m > n:
            return -1

        '''先求s[0,..,m]和t的编码值'''
        source, target = 0, 0
        mul = 1         # 最大幂次，即 base**(m-1)
        for i in range(m):
            source = ( source * base + encode(haystack[i]) ) % MOD     # s[:m]的哈希编码值
            target = ( target * base + encode(needle[i]) ) % MOD     # p的哈希编码值
            if i<m-1:   # 只计算 m-1次
                mul = mul * base % MOD

        if source == target:
                return 0

        '''枚举s[i]，求s中下一个长为m的连续子字符串的编码值'''
        # 维护一个长度为m的字符串滑动窗口：s[i-m+1, i]
        for i in range(m, n):
            source = ( source - encode(haystack[i-m]) * mul + MOD) * base % MOD   # 去掉s[i-m]
            source = ( source + encode(haystack[i]) ) % MOD                        # 加入s[i]

            if source == target:    # 找到了第一个，直接返回
                return i-m+1

        return -1

[NorthSeacoder]

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
    if (needle.length === 0) return 0
    //bf=>暴力算法
    let len = needle.length;
    for (let i = 0; i <= haystack.length - len; i++) {
        let subStr = haystack.slice(i, i + len);
        if (subStr === needle) return i
    }
    return -1
};

[JasonQiu]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(needle) == 0:
            return 0

        def get_kmp():
            i = 0
            kmp = [0] * len(needle)
            for j in range(1, len(needle)):
                while i > 0 and needle[j] != needle[i]:
                    i = kmp[i - 1]
                if needle[j] == needle[i]:
                    i += 1
                kmp[j] = i
            return [-1] + kmp[:-1]

        kmp = get_kmp()
        i, j = 0, 0
        while i < len(haystack) and j < len(needle):
            if haystack[i] == needle[j]:
                i, j = i + 1, j + 1
            else:
                j = kmp[j]
                if j == -1:
                     i, j = i + 1, j + 1

        return i - len(needle) if j == len(needle) and haystack[i - 1] == needle[len(needle) - 1] else -1

[joemonkeylee]

var strStr = function (haystack, needle) {
    let n = haystack.length
    let m = needle.length
    if (m === 0) return 0

    let next = new Array(m).fill(0)
    for (let i = 1, j = 0; i < m; i++) {
        while (j > 0 && needle[i] !== needle[j]) {
            j = next[j - 1]
        }
        if (needle[i] === needle[j]) {
            j++
        }
        next[i] = j
    }

    for (let i = 0, j = 0; i < n; i++) {
        while (j > 0 && haystack[i] !== needle[j]) {
            j = next[j - 1]
        }
        if (haystack[i] === needle[j]) {
            j++
        }
        if (j === m) {
            return i - m + 1
        }
    }
    return -1
};

[Abby-xu]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        A, B = len(haystack), len(needle)
        if A < B or B==0:
            return -1
        dictNeedle = {}
        dictNeedle[needle] = 1
        left, right = 0, B
        while right<=A:
            if haystack[left:right] in dictNeedle:
                return left
            left+=1
            right+=1
        return -1

[bookyue]

    public int strStr(String haystack, String needle) {
        int m = needle.length();
        int[] next = new int[m];

        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j))
                j = next[j - 1];

            if (needle.charAt(i) == needle.charAt(j))
                j++;

            next[i] = j;
        }

        for (int i = 0, j = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j))
                j = next[j - 1];

            if (haystack.charAt(i) == needle.charAt(j))
                j++;

            if (j == m) return i - m + 1;
        }

        return -1;
    }

[Lydia61]

28. 实现strStr

代码

经典KMP算法

代码

class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        for(int i = 0; i <= n - m; i++){
            int j = i, k = 0; 
            while(k < m and s[j] == p[k]){
                j++;
                k++;
            }
            if(k == m) return i;
        }
        return -1;
    }
};

[RestlessBreeze]

code

class Solution {
public:
    vector<int> buildMatch(string& needle)
    {
        vector<int> match(needle.length());
        match[0] = -1;
        for (int i = 1; i < needle.length(); i++)
        {
            int j = match[i - 1];
            while (j >= 0 && needle[j + 1] != needle[i])
            {
                j = match[j];
            }
            if (needle[j + 1] == needle[i])
            {
                match[i] = j + 1;
            }
            else
            {
                match[i] = -1;
            }
        }
        return match;
    }

    int kmp(string& haystack, string& needle)
    {
        int hlen = haystack.length();
        int nlen = needle.length();
        if (hlen < nlen)
            return -1;
        vector<int> match = buildMatch(needle);
        int hnow = 0;
        int nnow = 0;
        while (hnow < hlen && nnow < nlen)
        {
            if (haystack[hnow] == needle[nnow])
            {
                hnow++;
                nnow++;
            }
            else if (nnow > 0)
            {
                nnow = match[nnow - 1] + 1;
            }
            else
            {
                hnow++;
            }
        }
        return nnow == nlen ? (hnow - nlen) : -1;
    }

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