---

文章目录

• 28. 找出字符串中第一个匹配项的下标：
• • 样例 1：
  • 样例 2：
  • 提示：
• 分析：
• 题解：
• • rust
  • go
  • c++
  • c
  • python
  • java

---

28. 找出字符串中第一个匹配项的下标：

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

样例 1：

输入：
	haystack = "sadbutsad", needle = "sad"
	
输出：
	0
	
解释：
	"sad" 在下标 0 和 6 处匹配。
	第一个匹配项的下标是 0 ，所以返回 0 。

样例 2：

输入：
	haystack = "leetcode", needle = "leeto"
	
输出：
	-1
	
解释：
	"leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

• 1 <= haystack.length, needle.length <= 10⁴
• haystack 和 needle 仅由小写英文字符组成

---

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 字符串匹配，大部分的语言都有API，可以看看API的实现，但是API的实现一般主要是平衡，稳定，但不一定最高效。
• KMP是个高效的算法，但是受匹配字符串中重复子串的情况影响，有可能退化成比暴力匹配还慢。

---

题解：

rust

impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let needle = needle.as_bytes();
        let m = needle.len();
        let mut next = vec![0usize; m];
        let mut j = 0;

        for i in 1..m {
            while j > 0 && needle[i] != needle[j] {
                j = next[j - 1];
            }

            if needle[i] == needle[j] {
                j = j + 1;
            }

            next[i] = j;
        }

        j = 0;
        for (i, &c) in haystack.as_bytes().iter().enumerate() {
            while j > 0 && c != needle[j] {
                j = next[j - 1];
            }

            if c == needle[j] {
                j += 1;
            }

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

        return -1;
    }
}

---

go

func strStr(haystack string, needle string) int {
    n, m := len(haystack), len(needle)
	next := make([]int, m)

	for i, j := 1, 0; i < m; i++ {
		for j > 0 && needle[i] != needle[j] {
			j = next[j-1]
		}

		if needle[i] == needle[j] {
			j = j + 1
		}

		next[i] = j
	}

	for i, j := 0, 0; i < n; i++ {
		for j > 0 && haystack[i] != needle[j] {
			j = next[j-1]
		}

		if haystack[i] == needle[j] {
			j += 1
		}

		if j == m {
			return i - m + 1
		}
	}

	return -1
}

---

c++

class Solution {
public:
    int strStr(string haystack, string needle) {
        const int n = haystack.size(), m = needle.size();
        int next[m];
        next[0] = 0;

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

            if (needle[i] == needle[j]) {
                j = j + 1;
            }

            next[i] = j;
        }

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

            if (haystack[i] == needle[j]) {
                j += 1;
            }

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

        return -1;
    }
};

---

c

int strStr(char * haystack, char * needle){
    const int n = strlen(haystack), m = strlen(needle);
    int next[m];
    next[0] = 0;

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

        if (needle[i] == needle[j]) {
            j = j + 1;
        }

        next[i] = j;
    }

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

        if (haystack[i] == needle[j]) {
            j += 1;
        }

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

    return -1;
}

---

python

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

---

java

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

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

            if (needle.charAt(i) == needle.charAt(j)) {
                j = j + 1;
            }

            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 += 1;
            }

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

        return -1;
    }
}

---

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

---