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

[ZacheryCao]

Idea

KMP

Code

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(needle) == 0:
            return 0
        if len(haystack) == 0 or len(haystack) <len(needle):
            return -1
        nex = [0 for _ in range(len(needle))]
        nex[0] = -1
        k = -1
        j = 0
        while j < len(needle)-1:
            if k == -1 or needle[k]==needle[j]:
                k += 1
                j += 1
                if needle[k]!=needle[j]:
                    nex[j] = k
                else:
                    nex[j] = nex[k]
            else:
                k = nex[k]
        i, j = 0, 0
        while i < len(haystack) and j < len(needle):
            if j == -1 or haystack[i] == needle[j]:
                i+=1
                j+=1
            else:
                j = nex[j]
        if j == len(needle):
            return i - j
        else:
            return -1

Complexity:

Time: O(N) Space: O(N)

[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+1 == n{
            return i-j
        }
    }
    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
    }
}

[Tesla-1i]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(needle) == 0:
            return 0
        if len(haystack) == 0 or len(haystack) <len(needle):
            return -1
        nex = [0 for _ in range(len(needle))]
        nex[0] = -1
        k = -1
        j = 0
        while j < len(needle)-1:
            if k == -1 or needle[k]==needle[j]:
                k += 1
                j += 1
                if needle[k]!=needle[j]:
                    nex[j] = k
                else:
                    nex[j] = nex[k]
            else:
                k = nex[k]
        i, j = 0, 0
        while i < len(haystack) and j < len(needle):
            if j == -1 or haystack[i] == needle[j]:
                i+=1
                j+=1
            else:
                j = nex[j]
        if j == len(needle):
            return i - j
        else:
            return -1

[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

[CodingProgrammer]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(needle) == 0:
            return 0
        if len(haystack) == 0 or len(haystack) <len(needle):
            return -1
        nex = [0 for _ in range(len(needle))]
        nex[0] = -1
        k = -1
        j = 0
        while j < len(needle)-1:
            if k == -1 or needle[k]==needle[j]:
                k += 1
                j += 1
                if needle[k]!=needle[j]:
                    nex[j] = k
                else:
                    nex[j] = nex[k]
            else:
                k = nex[k]
        i, j = 0, 0
        while i < len(haystack) and j < len(needle):
            if j == -1 or haystack[i] == needle[j]:
                i+=1
                j+=1
            else:
                j = nex[j]
        if j == len(needle):
            return i - j
        else:
            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;
}

}

[ivangin]

code

public class ImplementstrStr {

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

[baddate]

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

[pwqgithub-cqu]

public class ImplementstrStr {

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

}

[charlestang]

思路

KMP

代码

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

        next = [0] * m

        i, j = 1, 0
        while i < m:
            if needle[i] == needle[j]:
                i += 1
                j += 1
                if i < m:
                    next[i] = j
            else:
                if j == 0:
                    i += 1
                else:
                    j = next[j]

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

[liuzekuan]

思路

设置两个指针i和j，分别用于指向主串(haystack)和模式串(needle) 从左到右开始一个个字符匹配 如果主串和模式串的两字符相等，则i和j同时后移比较下一个字符 如果主串和模式串的两字符不相等，就跳回去，即模式串向右移动，同时模式串指针归零(i = 1; j = 0) 所有字符匹配结束后，如果模式串指针指到串尾(j = needle.length)，说明完全匹配，此时模式串出现的第一个第一个位置为：i - j

代码

• 语言支持：Java

Java Code:

class Solution {
    public int strStr(String haystack, String needle) {
        char[] hayArr = haystack.toCharArray();
        char[] needArr = needle.toCharArray();
        int i = 0; //主串(haystack)的位置
        int j = 0; //模式串(needle)的位置
        while (i < hayArr.length && j < needArr.length) {
            if (hayArr[i] == needArr[j]) { // 当两个字符相等则比较下一个
                i++;
                j++;
            } else {
                i = i - j + 1; // 一旦不匹配，i后退
                j = 0; // j归零
            }
        }
        if (j == needArr.length) { //说明完全匹配
            return i - j;
        } else {
            return -1;
        }
    }
}

[LannyX]

思路

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

复杂度分析

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

[zhangzz2015]

思路

• 利用rolling hash 实现code。时间复杂度为 O(n+m)，空间复杂度为O(1)

关键点

代码

• 语言支持：C++

C++ Code:

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

        //  use rolling hash.                 
        if(needle.size() > haystack.size())
            return -1; 

        //   hash  a[0, n-1] = a[0] * k^(n-1) + .... a[n-1]
        //         a[1, n] =  prev * k  - a[0]* k^n + a[n]; 
        int sum =1; 
        int nhash =0; 
        int hhash =0; 
        int k = 26; 
        int prim = 1e7 + 7;
        int nsize = needle.size(); 
        for(int i=0; i< nsize; i++)
        {
            nhash = ( (nhash *k)%prim +  (needle[i]-'a'))%prim; 
            sum *= k; 
            sum = sum%prim; 
            hhash = ( (hhash*k)%prim + (haystack[i]-'a'))%prim ; 
        }

        if(nhash == hhash && isSameString(haystack, needle, 0) )
        {
            return 0; 
        }

        for(int i= nsize; i< haystack.size(); i++)
        {
            hhash = ( (hhash *k) %prim  -  (sum * (haystack[i-nsize]-'a') )%prim + (haystack[i] - 'a') + prim)%prim; 
            if(nhash == hhash && isSameString(haystack, needle, i -nsize+1))
                return i-nsize+1;             
        }

        return -1; 

    }

    bool isSameString(string& haystack, string & needle, int start)
    {   

       for(int i=0; i< needle.size(); i++)
       {
           if(haystack[start+i] != needle[i])
               return false;
       }
        return true;                 
    }
};

[1149004121]

28. 实现 strStr()

思路

KMP。

代码

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

复杂度分析

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

[falconruo]

思路:

KMP

复杂度分析:

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

代码(C++):

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

        if (haystack == needle || m == 0) return 0;

        vector<int> prefix(m + 1, 0);

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

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

        return -1;
    }
};

[Myleswork]

思路

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

代码

[alongchong]

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

[honeymeng-hub]

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

[callmeerika]

思路

KMP

代码

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

复杂度

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

[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

}

[hulichao]

思路

看起来是简单题就用双指针遍历来实现喽

代码

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0)
            return 0;
        int left = 0, right = 0, index = 0;
        while (right < haystack.length() && index < needle.length()) {
            if (haystack.charAt(right) != needle.charAt(index)) {
                left++;
                right = left;
                index = 0;
            } else {
                right++;
                index++;
            }
        }
        return index == needle.length() ? left : -1;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[hdyhdy]

func strStr(haystack, needle string) int {
    n, m := len(haystack), len(needle)
    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
        }
    }
    return -1
}

[Hacker90]

func strStr(haystack, needle string) int { n, m := len(haystack), len(needle) 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 } } return -1 }

[Today-fine]

又是美好学习的一天

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

[fornobugworld]

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

[Jay214]

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    // return needle.length>0?haystack.indexOf(needle):0; // 一句话搞定的暂时不用，用下面手撕的

    if(needle.length===0) return 0;
    for(let i=0;i<haystack.length;i++){
        if(haystack[i]===needle[0]){
            if(haystack.slice(i,i+needle.length)===needle){
                return i;
            }
        }
    }

    return -1;
};

[hx-code]

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

[machuangmr]

代码

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.isEmpty()) return 0;
        int n = haystack.length(), m = needle.length();
        // 构建 next数组
        // i 指针从1开始，j 指针从0开始就好
        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 < n;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;
    }
}

[zzzpppy]

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

[yetfan]

思路 kmp

代码

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

[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

[pwqgithub-cqu]

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

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