【LeetCode】【Rust】【KMP】【双指针】28. 实现 strStr()

题目：实现 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() 定义相符。

思路：

Rust 考虑到编码的不同，不能和Java一样用 .charAt()来获取到字符， 考虑到效率的问题，也不能直接用浮标获取字符 Rust先用let chars = haystack .Chars()转为字符组也不能用浮标，只能对chars进行遍历 无形之中用Rust写提高了一些难度 最后只能用haystack.as_bytes();获取字符数组，再进行处理

答案：

双指针 + 回溯：

impl Solution {
          
   
    pub fn str_str(haystack: String, needle: String) -> i32 {
          
   
        if (needle.len() == 0){
          
   
            return 0
        }
        let haystack = haystack.as_bytes();
        let needle = needle.as_bytes();
        let mut i =0;
        let mut j =0;
        
       
        while(i< haystack.len()){
          
   
            if(haystack[i] == needle[j]){
          
   
                println!("{},{},{}",haystack[i],i,j);
                if(j==needle.len()-1){
          
   
                    return (i-j) as i32;
                }
                j+=1;
                i+=1;
            }else if(j != 0){
          
   
                i=i-j+1;
                j=0;
            }else{
          
   
                i+=1;
            }
            
        }
        -1
    }
}

KMP： 不说了，类型转换转得我头疼，明明思路都有了，后面都在写类型转换，如果有更好的处理方法，请指教！！！

impl Solution {
          
   
    pub fn str_str(haystack: String, needle: String) -> i32 {
          
   
        if (needle.len() == 0){
          
   
            return 0
        }
        let haystack = haystack.as_bytes();
        let needle = needle.as_bytes();
        let mut i =0;
        let mut j:i32 =0;
        let mut next: Vec<i32> = Vec::new();
        for i in (0..needle.len()){
          
   
            next.push(0)
        }
        Self::getNext(&mut next,needle);
        while(i< haystack.len() && j < needle.len() as i32){
          
   
            if(j == -1 || haystack[i] == needle[j as usize]){
          
   
                j+=1;
                i+=1;
            }else {
          
   
                j = next[j as usize] ;
            }
            
        }
        if (j >= needle.len() as i32){
          
   
                return i as i32 -j
        }
        -1
    }

    fn getNext(next: &mut Vec<i32>,needle:&[u8]){
          
   
        let mut k: i32 = -1;
        let mut j: i32 = 0;
        next[0] = -1;
        while(j< needle.len() as i32 -1){
          
   
            if(k == -1 || needle[j as usize] == needle[k as usize]){
          
   
                k += 1;
                j += 1;
                next[j as usize] = k;  
            }else {
          
   
                k = next[k as usize] as i32;
            }
        }
        
    }
}

对了，我有个问题，是不是rust的提交，是不比运行时间的？？ 不管快还是慢，都是百分之百，好像刷了几道题都是这样子 希望有缘人看到了能帮我解答一下