首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    KMP与AC自动机详细讲解(带图)

    KMP​ 算法可以说是我学过的算法里最让我印象深刻的一个算法了。初学 KMP​​ 的时候真的是抓耳挠腮,硬啃了一下午的博客才勉强可以自己独立推一遍算法的整个流程。第二次学习 KMP​ 是为了在数据结构课上给同学们介绍这个算法,自己学和教会别人又是不一样的难度,于是我又重新学习了一遍,但这一次学习时有很多之前觉得很抽象的东西都突然茅塞顿开了,为了讲解的效果,我还反复推导了几次算法,确保讲课的流畅。第三次学习 KMP​ 是为了给集训队的学弟们讲这个算法,而竞赛更偏重于算法的应用,所以我在重新推演了一次算法后又找了一些经典例题。自此,对于 KMP 的理解可以说是挺明晰了。最近,我又学习了 AC自动机,很巧的是,AC自动机的思想和 KMP 是一样的,于是我又“被迫”重温了一遍 KMP ,既然那么有缘分,不如就写篇博客吧。

    03

    leetcode-3. 无重复字符的最长子串

    这道题要明确的一点是求最长子串而不是最长子序列。先对传进来的字符串长度进行判断,若传进来的字符串长度小于等于 1,则直接返回其长度即可,定义开始指针的位置,以及初始化最长字串的记录值,并将字符串转换为字符数组。开始遍历字符数组,外层从 1 开始,里层从 0 开始。   如果前后指针的字符一样,则重新定义开始的位置为当前的位置 +1,并跳出本次循环。每两次循环执行完后都要让当前字串长度与已记录的最长子串长度进行比较,由于 start 从 0 开始的,求真正的长度时要 +1,用三目运算判断当前最长的子串与已记录的最长子串的比较且重新定义最长子串,可能还是原来的最长,也可能是当前子串最长。待遍历完成后记录的最长字串即为所求,返回即可。

    04
    领券