LeetCode 28. 实现 strStr()（KMP、字符串）

末蓝、 2022-11-29 12:50 140阅读 0赞

**上一篇博客：[LeetCode 27. 移除元素（双指针）][LeetCode 27.]**

>  写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法，所以我打算从LeetCode简单的题目开始做起，攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[LeetCode 28. 实现 strStr()][LeetCode 28. _ strStr]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  示例
     *   *  示例 1
         *  示例 2
     *  说明
 *  题解
 *   *  暴力解法（滑动窗口）
     *   *  解题思路
         *  解题代码
         *  时间复杂度
         *  提交结果
     *  KMP解法
     *   *  解题思路
         *  解题代码
         *  时间复杂度
         *  提交结果

# 题目信息 #

## 题目描述 ##

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

# 题解 #

## 暴力解法（滑动窗口） ##

### 解题思路 ###

我们可以使用 **C++ STL** string类的 `compare()` 函数不断的从 **haystack** 取出长度为 `needle.length()` 的子串与 `needle` 进行比较，成功则返回当前子串的头指针即可。如果一直遍历到最后一个子串也没有匹配上的话就返回 **-1**。

在 **C++** 中使用 `compare()` 函数需要引入 `include<string>` 头文件。`compare()`函数主要有四个重载函数，在本题中我们使用的函数为：

int compare(index, length, &str );
    // index:子串的开始下标
    // length:子串的长度
    // &str:与子串进行比较的字符串

例如：

#include<iostream>
    #include<string>
    using namespace std;
    
    int main() { 
    	string str1, str2;
    	cin >> str1 >> str2;  // 输入str1, str2
    	cout << str1.compare(str2);  // 比较str1和str2
    	cout << endl;
    	
    	// 比较str1第一个与str2长度相等的子串与str2 
    	cout << str1.compare(0, str2.length(), str2); 
    	return 0; 
    }

在 `compare()` 函数返回的结果有三种：

*  返回值 `大于0` 说明 **str1 < str2**
 *  返回值 `等于0` 说明 **str1 == str2**
 *  返回值 `大于0` 说明 **str1 > str2**

`注意: compare() 是按照字符串的 字典序 进行比较的，并不是字符串的长度。`

明白了 `compare()` 函数的用法那么本题就很简单了，我们只要将长度为 `needle.length()` 的滑动窗口沿着 `haystack` 字符串逐步移动，并将窗口内的子串与 needle 字符串相比较，如果结果返回 **0** 说明匹配到了，那么我们直接返回开始的 **下标** 即可。如果函数遍历完整个字符串都没有匹配到说明没有与 `needle` 相同的子串，此时 `return -1` 即可。

![图解1][1]

### 解题代码 ###

class Solution { 
    public:
        int strStr(string haystack, string needle) { 
            int haystack_len = haystack.length(), needle_len = needle.length();
            for (int i = 0; i < haystack_len - needle_len + 1; i++) { 
                if (haystack.compare(i, needle_len, needle) == 0) return i;
            }
            return -1;
        }
    };

### 时间复杂度 ###

假设字符串 **haystack** 的长度为 **N**，**needle** 的长度为 **L**。因为需要依次进行滑动遍历，所以时间复杂度为 \**O((N - L)L)*

### 提交结果 ###

![提交结果][2020082108553297.png]

--------------------

## KMP解法 ##

### 解题思路 ###

本题也可以使用 **KMP算法** 来解决，KMP算法虽然在刚接触的时候不太好理解，但是是一种效率比较高的串的模式匹配算法。KMP算法可以在 **O(m + n)** 的时间数量级上完成串的匹配操作。相对于暴力解法，其改进在于不用依次进行循环遍历，而是利用已经得到的 `“部分匹配”` 的结果将比较的串向后 `"滑动”` 尽可能远的一段距离后继续进行匹配，省去了很多无用功。

有关 **KMP算法** 的具体实现大家可以看看B站UP主 **正月点灯笼** 的讲解视频：  
 [KMP字符串匹配算法1][KMP_1]  
 [KMP字符串匹配算法2][KMP_2]

灯神讲的非常好，其他的算法也讲的很棒，宝藏UP，强烈推荐哈哈。

### 解题代码 ###

class Solution { 
    public:
        int strStr(string haystack, string needle) { 
            if (needle.empty()) return 0;
    
            // 求前缀表
            vector<int> prefix_table(needle.length() + 1);
            prefix_table[0] = 0;
            int len = 0, i = 1;
            while (i < needle.length()) { 
                if (needle[i] == needle[len]) { 
                    len++;
                    prefix_table[i] = len;
                    i++;
                } else { 
                    if (len > 0) { 
                        len = prefix_table[len - 1];
                    } else { 
                        prefix_table[i] = len;
                        i++;
                    }
                }
            }
            // 将前缀表的向后移动一位，并将第一位改为 -1
            for (int j = prefix_table.size() - 1; j > 0; j--) { 
                prefix_table[j] = prefix_table[j - 1];
            }
            prefix_table[0] = -1;
    
            // KMP_search
            int k = 0, j = 0;
            while (k < haystack.length()) { 
                if (j == needle.length() - 1 && haystack[k] == needle[j]) { 
                    return k - j;
                }
                if (haystack[k] == needle[j]) { 
                    k++;
                    j++;
                } else { 
                    j = prefix_table[j];
                    if (j == -1) { 
                        k++;
                        j++;
                    }
                }
            }
            
            return -1;
        }
    };

### 时间复杂度 ###

**O(m +n)**

### 提交结果 ###

![提交情况][20200821120236197.png]  
这个提交结果让我感到很意外，竟然比暴力法击败数更低！但是不能否认 一般情况下 **KMP算法** 确实是比 **暴力算法** 要好很多。

--------------------

> 未完待续，持续更新中……  
> ![今天谁也别想阻止我好好学习][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]

[LeetCode 27.]: https://blog.csdn.net/qq_41575507/article/details/108082666
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[LeetCode 28. _ strStr]: https://leetcode-cn.com/problems/implement-strstr/
[1]: /images/20221124/dd5678fcdbf94b75b7ea98079761f8bc.png
[2020082108553297.png]: /images/20221124/20ea1c7b9769446e82d8c342d953f304.png
[KMP_1]: https://www.bilibili.com/video/BV1Px411z7Yo?t=965
[KMP_2]: https://www.bilibili.com/video/BV1hW411a7ys/?spm_id_from=333.788.videocard.0
[20200821120236197.png]: /images/20221124/de14a6ecaf8041449785a6251f2e7e0b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20221124/09eb25b19784442bae64056498138949.png