算法刷题Day9 | 28. 实现 strStr()、459.重复的子字符串、字符串总结

算法刷题Day9 | 28. 实现 strStr()、459.重复的子字符串、字符串总结

  • 🙋‍♂️ 作者:海码007
  • 📜 专栏:算法专栏
  • 💥 标题:算法刷题Day8 | 28. 实现 strStr()、459.重复的子字符串、字符串总结
  • ❣️ 寄语:书到用时方恨少,事非经过不知难!

0 引言

1 实现 strStr()

  • 🎈 文档讲解:https://programmercarl.***/0028.%E5%AE%9E%E7%8E%B0strStr.html
  • 🎈 视频讲解:最浅显易懂的 KMP 算法讲解
  • 🎈 做题状态:KMP算法的next数组的求解还是有点懵

1.1 我的解题

暴力解题:直接两个循环

class Solution {
public:
    int strStr(string haystack, string needle) {
        for(int i = 0; i < haystack.size(); i++)
        {
            int j = 0;
            for (; j < needle.size(); j++)
            {
                if (haystack[i+j] != needle[j])
                {
                    // 如果第一个数都不匹配,则直接跳出循环
                    break;
                }
            }
            // 如果全部的数都匹配,则此时 j == needle.size()
            if (j == needle.size())
            {
                return i;
            }
        }

        return -1;
    }
};

1.2 KMP算法解题

KMP的经典思想就是:当出现字符串不匹配时,可以记录一部分之前已经匹配的文本内容,利用这些信息避免从头再去做匹配。

如上图所示,只需要我们找到已经匹配过的字符串中前缀和后缀相等的个数,就知道下一次遍历,子串应该从哪个位置开始。例如下图中,在C处不匹配时,我们只需要找出 ABAB 这个字符串,最小的前后串相等的个数是多少,就知道下次遍历子串该从哪个位置开始。 对于 ABAB 字符串,可以得知最小前后串相等的个数是2。所以子串从 (2+1)的位置开始遍历,也就是从 索引为 2 的位置开始遍历。因为主串中末尾匹配的字符对应 ABAB 的后缀。而我们已经知道 ABAB 的 AB前缀和AB后缀是相等的。所以此时 AB 前缀也就不需要再和主串中末尾的 AB 进行比较了。

现在知道匹配的基本原理后,下一步的任务就是求解 前缀表 也就是子串中当前字符前面的字符串的相同前后缀的长度是多少。也就是next数组。

使用递推求解next数组:

next数组(前缀表)求解的步骤:
初始化、前后缀不相同的情况、前后缀相同的情况、更新next数组

  1. 初始化,两个索引值,分别指向前缀末尾(索引 j )和后缀末尾(索引 i )。首先初始化 j=0; next[0] = 0;
  2. 遍历 i ,当前后缀不相等时,
  

2 重复的子字符串

  • 🎈 文档讲解:https://programmercarl.***/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html
  • 🎈 视频讲解:https://www.bilibili.***/video/BV1M5411j7Xx/?spm_id_from=333.788&vd_source=d499e7f3a8e68e2b173b1c6f068b2147
  • 🎈 做题状态:

2.1 暴力求解

2.2 KMP求解法

3 字符串总结

字符串是若干字符组成的有限序列,也可以理解为是一个字符数组,但是很多语言对字符串做了特殊的规定,接下来我来说一说C/C++中的字符串。

在C语言中,把一个字符串存入一个数组时,也把结束符 '\0’存入数组,并以此作为该字符串是否结束的标志。
在使用 string 的时候直接把他看作一个字符数组会便于理解。

转载请说明出处内容投诉
CSS教程_站长资源网 » 算法刷题Day9 | 28. 实现 strStr()、459.重复的子字符串、字符串总结

发表评论

欢迎 访客 发表评论

一个令你着迷的主题!

查看演示 官网购买