【Day 83 】2022-03-04 - 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() 定义相符。

[ZacheryCao]

Idea

KMP

Code

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.size()==0) return 0;
        if(haystack.size()==0 or haystack.size()<needle.size()) return -1;
        vector<int> next((int) needle.size());
        int ans = -1;
        getNext(next, needle);
        int i=0, j =0;
        int l1 = haystack.size(), l2 = needle.size();
        while(i<l1 and j < l2){
            if(j==-1 or haystack[i]==needle[j]){
                ++j;
                ++i;
            }else{
                j = next[j];
            }
        }
        if(j == l2)
            return i-j;
        else
            return -1;
    }

    void getNext(vector<int>& next, string p){
        int l=p.size();
        int k = -1;
        int j = 0;
        next[0] = -1;
        while(j<l-1){
            if(k==-1 or p[j]==p[k]){
                ++k;
                ++j;
                if(p[j]!=p[k])
                    next[j] = k;
                else
                    next[j] = next[k];
            }
            else{
                k = next[k];
            }
        }
    }
};

Complexity:

Time: O(N+M). M: length of needle. N: length of haystack Space: O(M)

[CoreJa]

思路

• KMP：经典KMP算法，关键要理解next数组的含义与构建方法，next数组：真前后缀相等串的最大长度，同时也是在子串和原串匹配失败时的回退点(后缀匹配失败后，可以直接从前缀继续出发匹配)。它的本质就是动规数组，状态转移方程为：$next[i]=j$，而j的状态转移方程为$j=nextj-1$，相等时j+=1，j表示的其实是后缀的开头，i在滑动时j会试探其是否和i相同，相同则说明前后缀长度+1，不同则回退到上一个"保存点"，即前缀退一格去尝试。复杂度$O(m+n)$ 最好的记忆点是回忆子串aabaaf的next数组构建过程。从i=1开始遍历子串(i是潜在的后缀头)，前缀则从j=0开始，如果两者相等，j+=1，next[i]=j，如果不等则回退j，直到退到0(前缀和后缀无匹配)。构建next的过程和匹配的过程非常相似，甚至可以把next的构建看作是和自己在匹配。

代码

class Solution:
    # built-in：直接调库，应该也是KMP实现。
    def strStr1(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

    # 暴力法：直接双重循环，复杂度$O(m*n)$
    def strStr2(self, haystack: str, needle: str) -> int:
        n = len(needle)
        if n == 0:
            return 0
        for i in range(len(haystack)):
            if haystack[i:i + n] == needle:
                return i
        return -1

    # KMP：经典KMP算法，关键要理解next数组的含义与构建方法，next数组：真前后缀相等串的最大长度，同时也是在子串和原串匹配
    # 失败时的回退点(后缀匹配失败后，可以直接从前缀继续出发匹配)。它的本质就是动规数组，状态转移方程为：$next[i]=j$，
    # 而`j`的状态转移方程为$j=next[j-1](needle[i]!=needle[j])$，相等时`j+=1`，`j`表示的其实是后缀的开头，`i`在滑动时
    # `j`会试探其是否和`i`相同，相同则说明前后缀长度+1，不同则回退到上一个"保存点"，即前缀退一格去尝试。复杂度$O(m+n)$
    # 最好的记忆点是回忆子串`aabaaf`的next数组构建过程。从`i=1`开始遍历子串(i是潜在的后缀头)，前缀则从`j=0`开始，如果两
    # 者相等，`j+=1`，`next[i]=j`，如果不等则回退`j`，直到退到0(前缀和后缀无匹配)。构建next的过程和匹配的过程非常相似，
    # 甚至可以把next的构建看作是和自己在匹配。
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(needle)
        if n == 0:
            return 0
        dp = [0]
        j = 0
        for i in range(1, n):
            while j and needle[j] != needle[i]:
                j = dp[j - 1]
            if needle[i] == needle[j]:
                j += 1
            dp.append(j)
        j = 0
        for i in range(len(haystack)):
            while j and needle[j] != haystack[i]:
                j = dp[j - 1]
            if haystack[i] == needle[j]:
                j += 1
                if j == n:
                    return i - j + 1
        return -1

[Alexno1no2]

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

[Tesla-1i]

class Solution:
    def strStr1(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

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

    def strStr(self, haystack: str, needle: str) -> int:
        n = len(needle)
        if n == 0:
            return 0
        dp = [0]
        j = 0
        for i in range(1, n):
            while j and needle[j] != needle[i]:
                j = dp[j - 1]
            if needle[i] == needle[j]:
                j += 1
            dp.append(j)
        j = 0
        for i in range(len(haystack)):
            while j and needle[j] != haystack[i]:
                j = dp[j - 1]
            if haystack[i] == needle[j]:
                j += 1
                if j == n:
                    return i - j + 1
        return -1

[yan0327]

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

[xuhzyy]

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

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

[james20141606]

Day 83: 28. Implement strStr() (string, KMP)

• Problem Link

  • 28. Implement strStr()

• Ideas

  • brute force way or KMP

• Complexity: hash table and bucket

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

• Code

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

• other resources:
  • https://leetcode-cn.com/problems/implement-strstr/solution/python3-sundayjie-fa-9996-by-tes/
  • https://leetcode-cn.com/problems/implement-strstr/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/

[zjsuper]

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

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

[xinhaoyi]

class Solution { // KMP 算法 // ss: 原串(string) pp: 匹配串(pattern) public int strStr(String ss, String pp) { if (pp.isEmpty()) return 0;

    // 分别读取原串和匹配串的长度
    int n = ss.length(), m = pp.length();
    // 原串和匹配串前面都加空格，使其下标从 1 开始
    ss = " " + ss;
    pp = " " + pp;

    char[] s = ss.toCharArray();
    char[] p = pp.toCharArray();

    // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
    int[] next = new int[m + 1];
    // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
    for (int i = 2, j = 0; i <= m; i++) {
        // 匹配不成功的话，j = next(j)
        while (j > 0 && p[i] != p[j + 1]) j = next[j];
        // 匹配成功的话，先让 j++
        if (p[i] == p[j + 1]) j++;
        // 更新 next[i]，结束本次循环，i++
        next[i] = j;
    }

    // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
    for (int i = 1, j = 0; i <= n; i++) {
        // 匹配不成功 j = next(j)
        while (j > 0 && s[i] != p[j + 1]) j = next[j];
        // 匹配成功的话，先让 j++，结束本次循环后 i++
        if (s[i] == p[j + 1]) j++;
        // 整一段匹配成功，直接返回下标
        if (j == m) return i - m;
    }

    return -1;
}

}

[luhnn120]

思路

KMP算法

代码

var strStr = function(haystack, needle) {
    const n = haystack.length, m = needle.length;
    if (m === 0) {
        return 0;
    }
    const pi = new Array(m).fill(0);
    for (let i = 1, j = 0; i < m; i++) {
        while (j > 0 && needle[i] !== needle[j]) {
            j = pi[j - 1];
        }
        if (needle[i] == needle[j]) {
            j++;
        }
        pi[i] = j;
    }
    for (let i = 0, j = 0; i < n; i++) {
        while (j > 0 && haystack[i] != needle[j]) {
            j = pi[j - 1];
        }
        if (haystack[i] == needle[j]) {
            j++;
        }
        if (j === m) {
            return i - m + 1;
        }
    }
    return -1;
};

复杂度

时间复杂度 O(n+m) 空间复杂度 O(m)

[feifan-bai]

思路 1.String matching

代码

class Solution:
    def strStr(self, haystack: str, needle: str) -> 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

复杂度分析

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

[haixiaolu]

思路

暴力法 （Accepted） KMP真是看不懂

代码 / Python

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

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

复杂度

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

[Myleswork]

思路

kmp，这题甚至还是用python在做哈哈哈，有点久远了

代码

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0
        j = 0
        needle_nextval = self.get_nextval(needle)
        for i in range(len(haystack)):
            while j > 0 and haystack[i] != needle[j]:
                j = needle_nextval[j - 1]
            if haystack[i] == needle[j]:
                j += 1
            if j == len(needle):  #到头了，找到了
                return i - len(needle) + 1
        else: return -1

    def get_nextval(self, temp: str) -> str:
        j = 0
        next = [0] * len(temp)
        for i in range(1, len(temp), 1):
            while j > 0 and temp[i] != temp[j]:
                j = next[j - 1]
            if temp[i] == temp[j]:
                j += 1
            next[i] = j
        return next 

[yijing-wu]

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

[LannyX]

代码

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle == null || needle.isEmpty()){
            return 0;
        }
        int m = haystack.length(), n = needle.length();
        if(m < n){
            return -1;
        }
        for(int i = 0; i <= m - n; i++){
            String sub = haystack.substring(i, i + n);
            if(sub.equals(needle)){
                return i;
            }
        }
        return -1;
    }
}

复杂度分析

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

[1149004121]

28. 实现 strStr()

思路

滚动哈希。

代码

var strStr = function(A, B) {
    const n1 = A.length;
    const n2 = B.length;
    if(n1 < n2) return -1;
    if(n2 === 0) return 0;
    let mod = 10 ** 7 + 7;
    let base = 31;
    let mul = getMul(base, n2 - 1, mod);
    let hashB = 0;
    let hashA = 0;
    for(let i = 0; i < n2; i++){
        hashB = (hashB * base + B[i].charCodeAt() - "a".charCodeAt()) % mod;
        hashA = (hashA * base + A[i].charCodeAt() - "a".charCodeAt()) % mod;
    };
    if(hashA === hashB) return 0;
    for(let i = n2; i < n1; i++){
        hashA = ((hashA - (A[i - n2].charCodeAt() - "a".charCodeAt()) * mul % mod + mod) % mod * base + A[i].charCodeAt() - "a".charCodeAt()) % mod;
        if(hashA === hashB) return i - n2 + 1;
    };
    return -1;
};

function getMul(base, exp, mod){
    if(exp === 0) return 1
    let y = getMul(base, exp >> 1, mod) % mod;
    return (exp % 2 === 1 ? y * y % mod * base : y * y % mod);
}

复杂度分析

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

[Tao-Mao]

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

[zhiyuanpeng]

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

[zuiaiqun]

func strStr(haystack string, needle string) int {
    sizeA, sizeB := len(haystack), len(needle)
    if sizeA == 0 && sizeB == 0 {
        return 0
    }
    if sizeB > sizeA {
        return -1
    }

    for i := 0; i < sizeA; i++ {
        j := 0
        for ; j < sizeB; j++ {
            if i+j >= sizeA {
                return -1
            }
            if needle[j] != haystack[i+j] {
                break
            }
        }
        if j == sizeB {
            return i
        }
    }
    return -1
}

[Moin-Jer]

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

[C2tr]

class Solution: def strStr(self, haystack: str, needle: str) -> int: a=len(needle) b=len(haystack) if a==0: return 0 next=self.getnext(a,needle) p=-1 for j in range(b): while p>=0 and needle[p+1]!=haystack[j]: p=next[p] if needle[p+1]==haystack[j]: p+=1 if p==a-1: return j-a+1 return -1

[charlestang]

思路

Rabin-Karp 算法。

把一个字符串看作是一个 26进制的数字，每个字母一个数字。

但是考虑到字符串很长，则会超过整数的限制，可以用取模的方法。

使用了取模后，可能导致哈希碰撞，出现碰撞后，还是要逐个字母检查是否匹配。

代码

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

        mod = 13131
        h = 0
        nums = [ord(c) - ord('a') for c in needle]
        h1 = 0
        nums1 = [ord(c) - ord('a') for c in haystack]
        for i in range(m):
            num = nums[i]
            num1 = nums1[i]
            h = (h * 26 + num) % mod
            h1 = (h1 * 26 + num1) % mod
        if h == h1 and self.check(0, haystack, needle): return 0

        A = pow(26, m, mod)
        for i in range(1, n - m + 1):
            h1 = (h1 * 26 - nums1[i - 1] * A + nums1[i + m - 1]) % mod
            if h1 == h:
                if self.check(i, haystack, needle):
                    return i
        return -1

    def check(self, i: int, haystack: str, needle: str) -> bool:
        for j in range(len(needle)):
            if haystack[i + j] != needle[j]:
                break
        else:
            return True     
        return False

时间复杂度 O(n) 长的那个字符串长度是 n。

[JudyZhou95]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        lenA = len(haystack)
        lenB = 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

[zhangzz2015]

关键点

• KMP 方法，找prefix的方法和匹配方向基本相同，时间复杂度为O(n*m)，空间复杂度为O(n)

代码

• 语言支持：C++

C++ Code:

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

        // kmp . 
        if(haystack.size()< needle.size())
            return -1; 
        // build prefix.         
        vector<int> prefix(needle.size(), 0); 
        int right =1; 
        int left =0; 
        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++; 

        }

        // check match. 

        left =0; 
        right =0; 

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

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

            right++;             
        }

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

    }
};

[watchpoints]

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

[callmeerika]

思路

暴力破解

代码

var strStr = function (haystack, needle) {
  if (needle.length === 0) return 0;
  let p = 0;
  let res = -1;
  while (p < haystack.length) {
    while (haystack[p] !== needle[0]&& p < haystack.length) {
      p++;
    }
    for (let i = 0; i < needle.length; i++) {
      if (needle[i] !== haystack[p + i]) {
        break;
      }
      if (i === needle.length - 1) {
        return p;
      }
    }
    p++;
  }
  return res;
};

复杂度

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

[moirobinzhang]

Code:

public class Solution { public int StrStr(string haystack, string needle) { if (string.IsNullOrEmpty(needle)) return 0;

    for (int i = 0; i < haystack.Length - needle.Length + 1; i++)
    {
        if (haystack[i] != needle[0])
            continue;

        int cursorIndex = 0;
        while (cursorIndex < needle.Length)
        {
            if (haystack[i + cursorIndex] != needle[cursorIndex])
                break;

            cursorIndex++;
        }

        if (cursorIndex == needle.Length)
            return i;
    }       

    return -1;        
}

}

[guangsizhongbin]

func strStr(haystack string, needle string) int { n, m := len(haystack), len(needle)

// need 为空字符串时
if m == 0 {
    return 0
}

pi := make([]int, m)
for i, j := 1, 0; i < m ; i ++{
    for j > 0 && needle[i] != needle[j] {
        j = pi[j-1]
    }
    if needle[i] == needle[j] {
        j++
    }
    pi[i] = j
}

for i, j := 0, 0; i < n; i ++ {
    for j > 0 && haystack[i] != needle[j] {
        j = pi[j-1]
    }
    if haystack[i] == needle[j] {
        j++
    }
    if j == m {
        return i - m + 1
    }
}
// need 不存在
return - 1

}

[Toms-BigData]

func strStr(haystack string, needle string) int { sizeA, sizeB := len(haystack), len(needle) if sizeA == 0 && sizeB == 0 { return 0 } if sizeB > sizeA { return -1 }

for i := 0; i < sizeA; i++ {
    j := 0
    for ; j < sizeB; j++ {
        if i+j >= sizeA {
            return -1
        }
        if needle[j] != haystack[i+j] {
            break
        }
    }
    if j == sizeB {
        return i
    }
}
return -1

}

[fornobugworld]

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

[Hacker90]

func strStr(haystack string, needle string) int { sizeA, sizeB := len(haystack), len(needle) if sizeA == 0 && sizeB == 0 { return 0 } if sizeB > sizeA { return -1 }

for i := 0; i < sizeA; i++ { j := 0 for ; j < sizeB; j++ { if i+j >= sizeA { return -1 } if needle[j] != haystack[i+j] { break } } if j == sizeB { return i } } return -1 }

[yetfan]

代码

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

复杂度 时间 O(nm) 空间 O(1)

[Richard-LYF]

class Solution { public int strStr(String ss, String pp) { int n = ss.length(), m = pp.length(); char[] s = ss.toCharArray(), p = pp.toCharArray(); // 枚举原串的「发起点」 for (int i = 0; i <= n - m; i++) { // 从原串的「发起点」和匹配串的「首位」开始，尝试匹配 int a = i, b = 0; while (b < m && s[a] == p[b]) { a++; b++; } // 如果能够完全匹配，返回原串的「发起点」下标 if (b == m) return i; } return -1; } }

[hx-code]

" var strStr = function (haystack, needle) { if (needle.length === 0) return 0; let p = 0; let res = -1; while (p < haystack.length) { while (haystack[p] !== needle[0]&& p < haystack.length) { p++; } for (let i = 0; i < needle.length; i++) { if (needle[i] !== haystack[p + i]) { break; } if (i === needle.length - 1) { return p; } } p++; } return res; }; "

[ACcentuaLtor]

class Solution: def strStr(self, hay: str, nee: str) -> int: if nee == "": return 0 if len(hay) < len(nee): return -1 n,m = len(hay),len(nee) for i in range(n-m+1): if hay[i:i+m] == nee[:]: return i return -1

[hdyhdy]

func strStr(haystack string, needle string) int {

    l1 := len(haystack)
    l2 := len(needle)

    if l2 == 0 {
        return 0
    }
    if l1 == 0 || l1 < l2 {
        return -1
    }

    for i := 0; i <= l1 - l2; i++ {
        if haystack[i : i + l2] == needle {
            return i
        }
    }
    return -1
}

[for123s]

class Solution { public: vector next;

void queryNext(string needle)
{
    int n = needle.size();
    int k = -1, j = 0;
    next.assign(n,-1);
    while(j<n-1)
    {
        if(k==-1||needle[j]==needle[k])
        {
            k++;
            j++;
            if(needle[j]==needle[k])
                next[j] = next[k];
            else
                next[j] = k;
        }
        else
            k = next[k];
    }
}

int strStr(string haystack, string needle) {
    queryNext(needle);
    int i = 0, j = 0, hn = haystack.size(), nn = needle.size();
    while(i<hn&&j<nn)
    {
        if(j==-1||haystack[i]==needle[j])
        {
            i++;
            j++;
        }
        else
            j = next[j];
    }
    if(j==nn)
        return i - j;
    return -1;
}

};

[GaoMinghao]

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

[falconruo]

思路: 方法一、滑动窗口

复杂度分析: 方法一、

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

代码(C++):

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

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

        for (int i = 0; i <= n - m; ++i) {
            if (haystack[i] != needle[0]) continue;
            if (haystack.substr(i, m) == needle) return i;
        }

        return -1;
    }
};

[tian-pengfei]

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(haystack==needle)return 0;
        if(needle=="")return 0;
        int re = -1;
        int m = haystack.size();
        int n = needle.size();

        for (int i = 0; i < m&&i+n<=m; ++i) {
            if(haystack[i]==needle[0]){
                bool isSuccess=true;
                for (int j = 1; j < n; ++j) {
                    if (haystack[j+i]!=needle[j]){
                        isSuccess = false;
                        break;
                    }
                }
                if(isSuccess)return i;
            }
        }
        return re;

    }
};

[dahaiyidi]

Problem

[28. 实现 strStr()](https://leetcode-cn.com/problems/implement-strstr/)

实现 [strStr()](https://baike.baidu.com/item/strstr/811469) 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

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

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 [strstr()](https://baike.baidu.com/item/strstr/811469) 以及 Java 的 [indexOf()](https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#indexOf(java.lang.String)) 定义相符。

示例 1：

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

---

Note

• 除了一点点的匹配之外，还有KMP算法，KMP算法的讲解：https://www.zhihu.com/question/21923021/answer/281346746

• 需要从t字符中找出p

• 最重要的是要求出pattern的next数组（部分匹配表(Partial Match Table)数组，PMT）。为了方便，next[i]的数组代表着pattern[0, i - 1]的前缀子集和后缀子集的交集的最长字符串长度。在此处，字符串本身不是自己的子串。

• 有了next数组我们就可以在不匹配的地方（也就是t[i] != t[j]时），i保持不动，j则跳转到pattern中的next[j]位置，也就是下一个比较的是t[i] 和p[next[j]]是否相等

• 为什么是next[j]???（这是理解KMP算法的核心）

  • 当t[i] != t[j]时，t[i - j + 1,i]与p[0, j-1]是相同的，那么next[j] 代表着p[0, j-1]前缀子集和后缀子集的重合元素的最长长度。
  • 为了下一次不再从头开始比较，要寻找t[i]之前紧邻的某些字符串和p的前面几个字符是相同的，找到最长的这几个字符即可。举个例子：
  • 从下图中可以看到，从next数组中可以查询p[0, j-1]的前缀子集和后缀子集的最长重合元素是abab，即next[j] = 4， 在下一次比较中可以直接从next[j]=4开始比较，而同时i无需移动位置。

  

---

Complexity

n: 待匹配字符串的长度

m: pattern字符串的长度。

• 时间O：O(n+m)

• 空间O：O(m)

---

Python

C++

class Solution {
public:
    int strStr(string t, string p) {
        if(p == ""){
            return 0;
        }
        vector<int> next(p.size(), 0);
        next[0] = -1;
        int i = 0, j = -1;

        // 求next数组
        while(i < p.size() - 1){
            if(j == -1 || p[i] == p[j]){
                i++;
                j++;
                next[i] = j;
            }
            else{
                j = next[j];
            }
        }

        i = 0, j = 0;
        while(i < t.size() && j < (int) p.size()){
            if(j == -1 || t[i] == p[j]){
                i++;
                j++;
            }
            else{
                j = next[j];
            }
        }
        if(j == p.size()){
            return i - j;
        }
        else{
            return -1;
        }

    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[tian-pengfei]

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

        int n = needle.size();
        int m = haystack.size();
        if(n==0)return 0;
        vector<int> prefix(n);
        prefix_table(needle,prefix);
        int i =0,j=0;
        //使用while循环变好控制下标
        while (i<m){
            if(j==n-1&& haystack[i]==needle[j]){
                return i-j;
            }
            if(haystack[i]==needle[j]){
                i++;j++;
            }else{
                j = prefix[j];
                //如果第一个母没有匹配上，就会变成-1，那么大家 就都向后移动一位在从头开始匹配
                if(j==-1){
                    j=0;
                    i++;
                }
            }

        }
        return -1;

    }

    //前缀表的建立
    void prefix_table(string needle,vector<int>& prefix){
        int n = needle.size();
        prefix[0]=0;
        int i = 1;
        int len = 0; //上一个对称的长度
        while (i<n){
            if(needle[len] == needle[i]){
                len++;
                prefix[i] = len;

                i++;
            } else{
                if(len==0){
                    prefix[i] = 0;
                    i++;

                }else{
                    //寻找上一把的对称的前缀（后缀）的局部对称，然后再往下面进行匹配，通过len形成一个迭代循环
                    len = prefix[len-1];
                }

            }
        }

        for (int j = n-1; j >0; --j) {
            prefix[j] = prefix[j-1];
        }
        prefix[0]=-1;
    }

};

[declan92]

java

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){return 0;}
        if(needle.length()>haystack.length()){return -1;}
        char[] t = haystack.toCharArray();
        char[] s = needle.toCharArray();
        int i = 0, j = 0;
        int[] next = getNext(needle);
        while (i < t.length && j < s.length) {
            if (j == -1 || t[i] == s[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == s.length ) {
            return i - j;
        } else {
            return -1;
        }
    }

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

        }
        return next;
    }
}

时间:O(m+n),m为T串长度,n为P串长度; 空间:O(n),next数组;

[declan92]

java

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }
        if (needle.length() > haystack.length()) {
            return -1;
        }
        char[] t = haystack.toCharArray();
        char[] s = needle.toCharArray();
        int i = 0, j = 0;
        while (i < t.length && j < s.length) {
            if (t[i] == s[j]) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }
        if (j == s.length) {
            return i - j;
        } else {
            return -1;
        }
    }
}

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