KMP算法讲解视频(非常好)

  • 名称:KMP算法讲解视频(非常好
  • 分类:考研专业课  
  • 观看人数:加载中
  • 时间:2020/1/10 22:06:26
分享到:

KMP算法是主要用来做字符串的匹配,有一个文本次T和一个模式串P,就是拿模式串P去匹配文本串T。 匹配的步骤分为两步,先做模式串自身匹配,即求出next数组;然后在进行T与P的匹配。 那么可能会问,为什么要做模式串自身匹配,这么做的优点体现在哪里?next数组到底是干啥的?它的含义是什么?   怎么求next数组? T与P的匹配过程具体是怎么操作的?

KMP算法讲解视频(非常好)

KMP算法,具体谁发明的就不说了,它主要的用途就是查找字符串,查找字符串"ab"(目标字符串)在字符串"abc"(待查找字符串)中出现的位置。换句话说,就是查找字符串"abc"是否包含字符串"ab",如果包含,返回包含的起始位置

如下两个字符串:

str = "dabxabxababxabwabxad" (待查找字符串)

ptr = "abxabwabxad" (目标字符串)

需要计算str中是否含有ptr,如果有,返回str中出现的起始位置,如果没有,返回-1

通过肉眼观察我们发现,str中是包含ptr的