算法｜28. 找出字符串中第一个匹配项的下标（rust重拳出击）

---

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

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

样例 1

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

样例 2

输入
	haystack = "", needle = "leeto"
	
输出
	-1
	
解释
	"leeto" 没有在 "" 中出现所以返回 -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/ 博客原创~

---