【Day 83 】2021-12-01 - 28 实现 strStr(

[azl397985856]

28 实现 strStr(

入选理由

暂无

题目地址

[-BF&RK）

https://leetcode-cn.com/problems/implement-strstr/](-BF&RK）

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

[yanglr]

思路:

本题要求返回第2个串p在第1个串中第一次出现的位置, 如果不存在就返回-1。

KMP应该是这个题的最佳解法, 可以粗略地看成dp, 这样就很容易理解了。

方法: KMP算法

先在原串和模式串地开头插入一个字符(比如: #), 方便后面更新next数组的值。

next数组的含义:

next[i]: 字符串s的前缀串(s[1:i])与后缀串(s[j:len-1])相等时的最大长度len。 如果找到了, 就将next[i] 更新为len。

代码:

实现语言: C++

class Solution {
public:
    int strStr(string s, string p) {
        if (p.empty())
            return 0;
        int n = s.size(), m = p.size();
        s = '#' + s, p = '#' + p;

        int next[m + 1]; /* 数组元素next[i]含义: 字符串s的前缀串(s[1:j])与后缀串(s[k:len-1])相等时的最大长度len */
        memset(next, 0, sizeof(next));
        for (int i = 2, j = 0; i <= m; i++) /* 更新next数组 */
        {
            while (j != 0 && p[i] != p[j + 1])
                j = next[j];
            if (p[i] == p[j + 1])
                j++;
            next[i] = j;
        }
        // 匹配一下
        for (int i = 1, j = 0; i <= n; i++)
        {
            while (j != 0 && s[i] != p[j + 1])
                j = next[j];
            if (s[i] == p[j + 1])
                j++;
            if (j == m)
                return i - m;
        }

        return -1;
    }
};

复杂度分析:

• 时间复杂度: O(n)
• 空间复杂度: O(n)

[banjingking]

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

        int lenHaystack = haystack.length();
        int lenNeedle = needle.length();
        // needle equal to zero
        if(needle.length() == 0){
            return 0;
        }

        // haystack shorter than
        if(lenNeedle < lenNeedle){
            return -1;
        }

        for(int i = 0; i <  lenHaystack - lenNeedle + 1; i++){
            for(int j =0; j < lenNeedle; j++){
                if(haystack.charAt(i+j) != needle.charAt(j)){
                    break;
                }

            }
        }
    }
}

[skinnyh]

Note

• Brute force. Use python string slicing to compare strings.

Solution

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        len_h, len_n = len(haystack), len(needle)
        if len_n == 0: return 0
        if len_h < len_n: return -1
        for i in range(len_h - len_n + 1):
            if haystack[i:i + len_n] == needle:
                return i
        return -1

Time complexity: O(NM)

Space complexity: O(M) slicing creates a new string

[zhuzuojun]

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;
    }
};

[qixuan-code]

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

        for i in range(len(haystack)-len(needle)+1):
            if haystack[i:i+len(needle)] == needle:
                return i

        return -1

[zhy3213]

思路

dbq 先这样 我有罪

代码

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not len(needle):
            return 0
        try:
            return haystack.index(needle)
        except Exception:
            pass    
        return -1

[falconruo]

思路: 滑动窗口

复杂度分析:

• 时间复杂度: O(N * M)，N为字符串haystack的长度, M为字符串needle的长度
• 空间复杂度: O(1)

代码(C++):

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.length();
        int n = needle.length();

        if (m < n) return -1;
        if (n == 0) return 0;

        int i = 0, j = 0, left = 0;

        while (i < m && j < n) {
            if (haystack[i] == needle[j]) {
                ++i;
                ++j;
            } else {
                left++;
                i = left;
                j = 0;
            }
        }

        if (j == n) return left;

        return -1;
    }
};

[yingliucreates]

link:

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

代码 Javascript

const strStr = function (haystack, needle) {
  if (haystack === needle || needle === '') {
    return 0;
  }
  for (let i = 0; i < haystack.length; i++) {
    if (haystack[i] === needle[0]) {
      let temp = haystack.substring(i, i + needle.length);
      if (temp === needle) {
        return i;
      }
    }
  }
  return -1;
};

[leo173701]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not len(needle):
            return 0
        try:
            return haystack.index(needle)
        except Exception:
            pass    
        return -1

[yachtcoder]

偷个懒 - -

class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        lenA, lenB = len(haystack), len(needle)
        if not lenB:
            return 0
        if lenB > lenA:
            return -1

        for i in range(lenA - lenB + 1):
            if haystack[i:i + lenB] == needle:
                return i
        return -1

[littlemoon-zh]

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

        for i in range(len(haystack) - len(needle) + 1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1

[ZacheryCao]

Idea:

KMP

Code:

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0
        if not haystack:
            return -1 if needle else 0
        p_needle = self.pStr(needle)
        i, j = 0, 0
        while i < len(haystack):
            if j < len(needle) and haystack[i] == needle[j]:
                j += 1
            else:
                if j == len(needle):
                    return i - j
                while j > 0 and haystack[i] != needle[j]:
                    j = p_needle[j-1]
                j += int(haystack[i] == needle[j])
            i += 1
        return i - j if j == len(needle) else -1

    def pStr(self, pattern):
        n = len(pattern)
        if n < 2:
            return [0]
        dp = [0]*n
        i, j =1, 0
        while i < len(pattern):
            if pattern[i] == pattern[j]:
                dp[i] = j + 1
                j += 1
            else:
                while pattern[i] != pattern[j] and j > 0:
                    j = dp[j-1]
                j += int(pattern[i] == pattern[j])
                dp[i] = j
            i += 1
        return dp

Complexity:

Time: O(M +N). M: length of pattern. N: length of string. Sace: O(M)

[zhangzz2015]

思路

• 有两种方法用来做字符串匹配，一种是KMP，一种为rolling hash。 KMP的核心思想，当如果发现 当前 s[i] != t[j]，不回退到原点重新比较，而是利用prefix ，拿到前一个字符的前缀相同的位置继续比较。时间复杂度为O(n +m )，空间复杂度为O(m) n 为目标串的大小，m 为匹配串的大小。

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int strStr(string haystack, string needle) {

        //  kmp method. 
        // calculate prefix. 

        if(haystack.size()< needle.size())
            return -1; 

        vector<int> prefix(needle.size(), 0); 
        int left =0; 
        int right =1; 

        // sliding windows. 
        while(right < needle.size())
        {
            while(left>0 && needle[left] != needle[right])
            {
                left = prefix[left-1]; 
            }

            if(needle[left]==needle[right])
                left ++;

            prefix[right] = left; 
            right++;             
        }

        left =0; 
        right =0; 

        while(left < haystack.size() && right < needle.size())
        {
            while(right>0 && haystack[left] != needle[right] )
            {
                right = prefix[right-1]; 
            } 

            if(haystack[left] == needle[right] )
                right++; 

            left++; 
        }

        if(right == needle.size())
        {
            return  left - right; 
        }
        else
            return -1; 

    }
};

[siyuelee]

BF

class Solution(object):
    def strStr(self, haystack, needle):
        len1, len2 = len(haystack), len(needle)
        if len2 == 0:
            return 0
        if len1 < len2:
            return -1
        for i in range(len1 - len2 + 1):
            if haystack[i:(i + len2)] == needle:
                return i
        return -1

[tongxw]

思路

暴力查找

代码

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle == null || needle.isEmpty()) {
          return 0;
        }

        int m = haystack.length();
        int n = needle.length();
        if (m < n) {
            return -1;
        }

        for (int i=0; i<=m-n; i++) {
            String subStr = haystack.substring(i, i + n);
            if (subStr.equals(needle)) {
                return i;
            }
        }

        return -1;
    }
}

• TC: O((m-n) * n)
• SC: O(1)

[biancaone]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0
        if not haystack:
            return -1
        if len(needle) > len(haystack):
            return -1
        m, n = len(haystack), len(needle)
        # 这个地方举个例子
        for i in range(m - n + 1):
            j = 0
            while j < n:
                if haystack[i + j] != needle[j]:
                    break
                j += 1
            if j == n:
                return i

        return -1

[ai2095]

28. Implement strStr()

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

Topics

-slide window

思路

slide window

代码 Python

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack) - len(needle) + 1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1

复杂度分析

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

[Daniel-Zheng]

思路

暴力。

代码(C++)

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (haystack.length() < needle.length()) {
            return -1;
        }
        else {
            for (int i=0; i<haystack.length()-needle.length()+1; i++) {
            if (haystack.substr(i, needle.length()) == needle) return i;
        }
        return -1;
        }
    }
};

复杂度分析

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

[JiangyanLiNEU]

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0){
            return 0;
        }else{
            for (int index=0; index<=haystack.length()-needle.length(); index++){
                if (haystack.substring(index, index+needle.length()).equals(needle)){
                    return index;
                }
            }
        }
        return -1;
    }
}

var strStr = function(haystack, needle) {
    if (needle.length==0){return 0};
    for (let index=0; index<=haystack.length-needle.length; index++){
        if (haystack.slice(index, index+needle.length) === needle){
            return index;
        };
    };
    return -1;
};

[kidexp]

thoughts

KMP

code

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if haystack and needle:
            def compute_next(needle):
                next_list = [-1]
                i, j = 0, -1
                while i < len(needle):
                    if j == -1 or needle[i] == needle[j]:
                        i += 1
                        j += 1
                        next_list.append(j)
                    else:
                        j = next_list[j]
                return next_list
            next_list = compute_next(needle)
            i = j = 0
            while i < len(haystack) and j < len(needle):
                if j == -1 or haystack[i] == needle[j]:
                    i += 1
                    j += 1
                else:
                    j = next_list[j]
            if j == len(needle):
                return i - j 
        return -1 if needle else 0

complexity

Time O(m+n)

Space O(1)

[thinkfurther]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle == "": return 0
        try:
            return haystack.index(needle)
        except ValueError:
            return -1

[Bingbinxu]

思路 滑动窗口 代码(C++)

实现语言: C++
class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.length();
        int n = needle.length();
        if (m < n) return -1;
        if (n == 0) return 0;       
        int i = 0, j = 0, left = 0;      
        while (i < m && j < n) {
            if (haystack[i] == needle[j]) {
                ++i;
                ++j;
            } else {
                left++;
                i = left;
                j = 0;
            }
        }         
        if (j == n) return left;       
        return -1;
    }
};

复杂度分析 时间复杂度: O(N×M) 空间复杂度: O(1）

[shawncvv]

思路

滚动哈希

代码

Python3 Code

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not haystack and not needle:
            return 0
        if not haystack or len(haystack) < len(needle):
            return -1
        if not needle:
            return 0
        hash_val = 0
        target = 0
        prime = 101
        for i in range(len(haystack)):
            if i < len(needle):
                hash_val = hash_val * 26 + (ord(haystack[i]) - ord("a"))
                hash_val %= prime
                target = target * 26 + (ord(needle[i]) - ord("a"))
            else:
                hash_val = (
                    hash_val - (ord(haystack[i - len(needle)]) - ord("a")) * 26 ** (len(needle) - 1)
                ) * 26 + (ord(haystack[i]) - ord("a"))
                hash_val %= prime
            if i >= len(needle) - 1 and hash_val == target:
                return i - len(needle) + 1
        return 0 if hash_val == target else -1

复杂度

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

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

[Serena9]

代码

class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        lenA, lenB = len(haystack), len(needle)
        if not lenB:
            return 0
        if lenB > lenA:
            return -1

        for i in range(lenA - lenB + 1):
            if haystack[i:i + lenB] == needle:
                return i
        return -1

[shamworld]

var strStr = function(haystack, needle) {
    if(needle=="") return 0;
    //循环haystack，拿到每一项
    for(let i=0;i<haystack.length;i++){
        //判断haystack和needle首位相等的地方,那么从此刻的位置开始循环判断haystack和needle是否完全相等
        if(haystack[i]==needle[0]){
            let count=0;
            //遍历needle
            for(let j=0;j<needle.length;j++){
                //每一次判断相等，都用count几下相等的次数，如果count的大小等于needle的长度，说明在haystack中存在完整的needle，即return 当前的i
                if(haystack[j+i]==needle[j]){
                    count++;
                    if(count==needle.length){
                        return i;
                    }
                }
            }
        }
    }
    return -1;
};

[HondryTravis]

思路

纯暴力匹配

代码

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
  const lenA = haystack.length
  const lenB = needle.length

  if (lenB === 0) return 0

  for (let i = 0; i < lenA; i ++) {
    const curStr = haystack.slice(i, i + lenB)
    if (curStr === needle) return i
  }

  return -1
};

复杂度分析

时间复杂度 O(M*N) [M,N 分别是两个字符串的长度]

空间复杂度 O(1)

[wenlong201807]

代码块

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++) {
    // 如果当前i 和 j不一致，就回退到上一个相等的位置的下一个看看是否匹配
    // 会不断回退，0为回退到边界，当回退到0意味着要重新从头开始匹配
    while (j > 0 && haystack[i] !== needle[j]) {
      j = next[j - 1];
    }
    if (haystack[i] === needle[j]) {
      j++;
    }
    // 当j 和 m的长度相等时，就说明存在
    if (j === m) {
      return i - m + 1;
    }
  }
  return -1;
};

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[ghost]

题目

28. Implement strStr()

代码

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

        if len(needle) > len(haystack):
            return -1

        for i in range(len(haystack) - len(needle) +1):
            if haystack[i:i+len(needle)] == needle: return i

        return -1

复杂度

Space: O(1) Time: O(N * M)

[Francis-xsc]

思路

暴力

代码

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

复杂度分析

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

[ychen8777]

思路

暴力 依次截取 haystack 中的 substring 和 needle 比较

代码

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

        if (needle == "") {
            return 0;
        }

        // if (haystack == "") {
        //     return -1;
        // }

        int i = 0, n = needle.length();
        while(i <= haystack.length() - n) {

            if (haystack.substring(i, i+n).equals(needle)) {
                return i;
            }

            i++;

        }

        return -1;      
    }
}

复杂度

时间: O(m * n) \ 空间: O(n)

[learning-go123]

思路

• 滑动窗口

代码

• 语言支持：Go

Go Code:

func strStr(haystack string, needle string) int {
    if len(needle) == 0 {
        return 0
    }
    if len(haystack) < len(needle) {
        return -1
    }

    i, j := 0, 0
    for i < len(haystack) && j < len(needle) {
        if haystack[i] == needle[j] {
            i++
            j++
        } else {
            i = i - j + 1
            j = 0
        }
    }

    if j == len(needle) {
        return i - j
    }
    return -1
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

[akxuan]

        if (!haystack || !needle) return -1;
        for (int i = 0; ; ++i) {
            for (int j = 0; ; ++j) {
                if (needle[j] == 0) return i;
                if (haystack[i + j] == 0) return -1;
                if (haystack[i + j] != needle[j]) break;
            }
        }
    }

[QiZhongdd]

var strStr = function(haystack, needle) {
    const n = haystack.length, 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;
};

[ysy0707]

思路：BF

1.暴力匹配
class Solution {
    //BF
    public int strStr(String haystack, String needle) {
        int haylen = haystack.length();
        int needlen = needle.length();
        //特殊情况:模式串长度大于主串长度or模式串为 0
        if(haylen < needlen){
            return -1;
        }
        if(needlen == 0){
            return 0;
        }
        //主串
        for(int i = 0; i < haylen - needlen + 1; i++){
            int j;
            //模式串
            for(j = 0; j < needlen; j++){
                //不符合时直接跳出，主串指针后移一位
                if(haystack.charAt(i + j) != needle.charAt(j)){
                    break;
                }
            }
            //匹配成功
            if(j == needlen){
                return i;
            }
        }
        return -1;
    }
}

时间复杂度: O(M * N) 空间复杂度: O(N)

[KennethAlgol]

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle == null || needle.isEmpty()) {
          return 0;
        }

        int m = haystack.length();
        int n = needle.length();
        if (m < n) {
            return -1;
        }

        for (int i=0; i<=m-n; i++) {
            String subStr = haystack.substring(i, i + n);
            if (subStr.equals(needle)) {
                return i;
            }
        }

        return -1;
    }
}

[KennethAlgol]

语音

java

class Solution {
    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();

        if (m < n) return -1;
        if (n == 0) return 0;

        int i = 0, j = 0, left = 0;

        while (i < m && j < n) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                ++i;
                ++j;
            } else {
                left++;
                i = left;
                j = 0;
            }
        }

        if (j == n) return left;

        return -1;
    }

}

语言

C++

public:
    public int strStr(string haystack, string needle) {
        int m = haystack.length();
        int n = needle.length();

        if (m < n) return -1;
        if (n == 0) return 0;

        int i = 0, j = 0, left = 0;

        while (i < m && j < n) {
            if (haystack[i] == needle[j]) {
                ++i;
                ++j;
            } else {
                left++;
                i = left;
                j = 0;
            }
        }

        if (j == n) return left;

        return -1;
    }
};

语言

java

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

[yan0327]

func strStr(haystack string, needle string) int {
    if len(needle) == 0{
        return 0
    }
    next := make([]int,len(needle))
    getNext(next, needle)
    j := -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{
            return i-len(needle)+1
        }
    }
    return -1
}
func getNext(next []int,s string){
    j := -1
    next[0] = j
    for i:=1;i<len(s);i++{
        for j>=0&&s[j+1]!=s[i]{
            j = next[j]
        }
        if s[j+1] == s[i]{
            j++
        }
        next[i] = j
    }
}

[joeytor]

思路

使用 滚动哈希的算法

维持一个 滑动窗口, 每次计算窗口的哈希值, 因为有 26 个字母, 所以用 26 进制来表示哈希值,

对于大于等于 len(needle) 开始的窗口, 需要将第一个的值在哈希值中去除, 然后加入最后一个的哈希值

当 i ≥ len(needle) -1 的时候, 可以尝试 hashval == target, 如果相等代表找到了匹配的字符串, 那么返回 index, 否则继续循环

如果循环结束还没有找到, 那么返回 -1

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

        hashval, target = 0, 0
        prime = 10000000000000003
        l = len(needle)

        for i in range(len(haystack)):
            if i < l:
                hashval = hashval * 26 + (ord(haystack[i]) - ord('a'))
                target = target * 26 + (ord(needle[i]) - ord('a'))
                hashval %= prime
                target %= prime
            else:
                # remove hash of first element
                hashval = hashval - (ord(haystack[i-l]) - ord('a')) * 26**(l-1)
                # add hash of new element
                hashval = hashval * 26 + (ord(haystack[i]) - ord('a'))
                hashval %= prime

            if i >= len(needle)-1:
                if hashval == target:
                    return i-len(needle)+1

        return -1

复杂度

待匹配串长度为 m, 模式串长度为 n

时间复杂度: O(m+n) target 窗口的复杂度是 O(n), 主串滑动窗口的复杂度是 O(m)

空间复杂度: O(1)

[pophy]

思路

• KMP

Java Code

class Solution {
    public int strStr(String s, String p) {
        int n = s.length();
        int m = p.length();
        if (m == 0) return 0;
        int[] suffix = preProcessing(p);
        int[] dp = new int[n];

        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && s.charAt(i) != p.charAt(j)) {
                j = suffix[j - 1];
            }
            if (s.charAt(i) == p.charAt(j)) {
                dp[i] = j + 1;
                j++;
            }
            if (dp[i] == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
    private int[] preProcessing(String str) {
        int[] dp = new int[str.length()];
        for (int i = 1; i < str.length(); i++) {
            int j = dp[i - 1];
            while (j >= 1 && str.charAt(i) != str.charAt(j)) {
                j = dp[j - 1];
            }
            if (str.charAt(i) == str.charAt(j)) {
                dp[i] = j + 1;
            }
        }
        return dp;
    }
}

时间&空间

• 时间 O(n)
• 空间 O(n)

[hellowxwworld]

int strStr(char *haystack, char *needle) {
    char *p, *q, *t, *pIter;
    for (pIter = haystack, p = needle; *p != '\0'; p++, pIter++);
    pIter--;
    for (p = haystack; *pIter != '\0'; pIter++, p++) {
        q = p;
        t = needle;
        while (*q == *t && *t) {
            q++;
            t++;
        }
        if (*t == '\0')
            return (p - haystack);
    }
    return -1;
}

[zhangzhengNeu]

使用 滚动哈希的算法

维持一个 滑动窗口, 每次计算窗口的哈希值, 因为有 26 个字母, 所以用 26 进制来表示哈希值,

对于大于等于 len(needle) 开始的窗口, 需要将第一个的值在哈希值中去除, 然后加入最后一个的哈希值

当 i ≥ len(needle) -1 的时候, 可以尝试 hashval == target, 如果相等代表找到了匹配的字符串, 那么返回 index, 否则继续循环

如果循环结束还没有找到, 那么返回 -1

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

    hashval, target = 0, 0
    prime = 10000000000000003
    l = len(needle)

    for i in range(len(haystack)):
        if i < l:
            hashval = hashval * 26 + (ord(haystack[i]) - ord('a'))
            target = target * 26 + (ord(needle[i]) - ord('a'))
            hashval %= prime
            target %= prime
        else:
            # remove hash of first element
            hashval = hashval - (ord(haystack[i-l]) - ord('a')) * 26**(l-1)
            # add hash of new element
            hashval = hashval * 26 + (ord(haystack[i]) - ord('a'))
            hashval %= prime

        if i >= len(needle)-1:
            if hashval == target:
                return i-len(needle)+1

    return -1

[XinnXuu]

Code

class Solution {
    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();
        if (m == 0 && n == 0) {
            return 0;
        }
        for (int i = 0; i < m - n + 1; i++){
            boolean flag = true;
                for (int j = 0; j < n; j++){
                    if (haystack.charAt(i + j) != needle.charAt(j)){
                        flag = false;
                        break;
                    }
                }
                if (flag == true) {
                return i;
            }
        }
    return -1;
     }
}

Complexity

• Time Complexity: O(MN)
• Space Complexity: O(1)

[Moin-Jer]

思路

---

KMP

代码

---

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

复杂度分析

---

• 时间复杂度：O(n + m), n 是 haystack 的长度，m 是 needle 的长度
• 空间复杂度：O(n)

[biscuit279]

思路：暴力法

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        m = len(haystack)
        n = len(needle)
        if  n==0:
            return 0
        if n>m:
            return -1
        if n==m:
            if haystack==needle:
                return 0
            else:
                return -1
        for i in range(0,m-n+1):
            if haystack[i:i+n] == needle:
                return i
        return -1

时间复杂度：O（mn） 空间复杂度：O（1）

[hewenyi666]

题目名称

76. 最小覆盖子串

题目链接

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

题目思路

code for Python3

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:

        # Func: 计算偏移表
        def calShiftMat(st):
            dic = {}
            for i in range(len(st)-1,-1,-1):
                if not dic.get(st[i]):
                    dic[st[i]] = len(st)-i
            dic["ot"] = len(st)+1
            return dic

        # 其他情况判断
        if len(needle) > len(haystack):return -1
        if needle=="": return 0

        # 偏移表预处理    
        dic = calShiftMat(needle)
        idx = 0

        while idx+len(needle) <= len(haystack):

            # 待匹配字符串
            str_cut = haystack[idx:idx+len(needle)]

            # 判断是否匹配
            if str_cut==needle:
                return idx
            else:
                # 边界处理
                if idx+len(needle) >= len(haystack):

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(N)

[hwpanda]

const strStr = (haystack, needle) => haystack.indexOf(needle);

[RocJeMaintiendrai]

代码

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle == null || needle.length() == 0) return 0;
        for(int i = 0; i < haystack.length(); i++) {
            if(i + needle.length() > haystack.length()) {
                break;
            }
            for(int j = 0; j < needle.length(); j++) {
                if(haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
                if(j == needle.length() - 1) {
                    return i;
                }
            }
        }
        return -1;
    }
}

复杂度分析

时间复杂度

O(mn)

空间复杂度

O(1)

[zhangyalei1026]

代码

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

复杂度分析

时间复杂度： O(NM) 空间复杂度：O(1)

[user1689]

题目

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

思路

滚动哈希(RK)

python3

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(haystack) == 0 and len(needle) == 0:
            return 0
        if len(haystack) == 0 or len(haystack) < len(needle):
            return -1
        if len(needle) == 0:
            return 0
        hash_val = 0
        prime = 100000007
        target = 0

        for i in range(0, len(haystack)):
            if (i < len(needle)):
                hash_val = hash_val * 26 + (ord(haystack[i]) - ord("a"))
                hash_val %= prime
                target = target * 26 + (ord(needle[i]) - ord("a"))
                target %= prime
            else:
                hash_val = (
                     hash_val - (ord(haystack[i - len(needle)]) - ord("a")) * 26 ** (len(needle) - 1)
                     ) * 26 + (ord(haystack[i]) - ord("a"))
                hash_val %= prime
            if (i >= len(needle) - 1) and (hash_val == target):
                return i - len(needle) + 1
        return 0 if hash_val == target else -1

复杂度分析

• time n + m
• space 1

相关题目

1. https://leetcode-cn.com/problems/longest-duplicate-substring/
2. https://leetcode-cn.com/problems/shortest-palindrome/
3. https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
4. https://leetcode-cn.com/problems/longest-chunked-palindrome-decomposition/
5. https://leetcode-cn.com/problems/distinct-echo-substrings/
6. https://leetcode-cn.com/problems/longest-happy-prefix/

[liuyangqiQAQ]

KMP

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(j == -1 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            }else {
                j = next[j];
            }
        }
        if(j == needle.length()) {
            return i - j;
        }
        return -1;
    }

    public int[] getNext(String p) {
        int[] next = new int[p.length()];
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < p.length() - 1){
            if(k == -1 || p.charAt(j) == p.charAt(k)) {
                k++;
                j++;
                if(p.charAt(j) != p.charAt(k)) {
                    next[j] = k;
                }else {
                    next[j] = next[k];
                }
            }else {
                k = next[k];
            }
        }
        return next;
    }
}