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

题目描述

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

解题思路

KMP 对我来说太烧脑了，不得不写点笔记

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

因为前缀表要求的就是相同前后缀的长度

定义两个指针i和j

• j指向前缀末尾位置(不包含)
• i指向后缀末尾位置(包含)

next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是j）

void getNext(int* next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 对当前字符串，j指向上一个字符串的最大前后缀的位置
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j ++ ;
        }
        next[i] = j; // 赋值
    }
}

举例

     j
 aabaabaaf
         i
 012345678
  0 01234

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let n = needle.len();
        let mut next = vec![0; n];
        let hay = haystack.chars().collect::<Vec<char>>();
        let s = needle.chars().collect::<Vec<char>>();
        let mut j = 0;
        for i in 1..n {
            while j >= 1 && s[i] != s[j] {
                j = next[j - 1];
            }
            if s[i] == s[j] {
                j += 1;
            }
            next[i] = j;    // next 表示以i结尾的字符串最大前后缀长度
        }
        // dbg!(&next);
        // build next ok
        if n == 0 { return 0 }
        j = 0;
        for i in 0..hay.len() {
            // dbg!(i, j);
            while j >= 1 && hay[i] != s[j] {
                j = next[j - 1];
            }
            if hay[i] == s[j] {
                j += 1;
            }
            if j == n {
                return (i + 1 - n) as i32
            }
        }
        -1
    }
}
}

学习感想

还得学习复习

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        if let Some(x) = haystack.find(&needle) {
            x as i32
        } else {
            -1i32
        }
    }
}

}