526互联

王道408---DS---串

发布时间 2023-10-29 14:17:40作者: TLSN

主要内容就是KMP算法

KMP

串的一些基本概念

1、子串/模式串

串中任意多个连续的字符组成的子系列叫做字串

2、主串

包含字串的串称为主串

3、模式匹配(pattern matching)

字串的定位操作称为串的模式匹配，是求子串在主串中的位置

算法

参考: https://www.bilibili.com/video/BV19C4y157dH/?spm_id_from=333.999.0.0&vd_source=87f7ad8544d4c3ad070c5c2ff28b7698

image-20231022173406509

  1. 首先写出PM(Partial Match)部分匹配值
  2. 写出next数组(next数组可分为两种，一种是下标从0开始，一种是下表从1开始)，需要注意的是next数组与PM数组总是错位一格
  3. 写出nextval

nextval原理如下:

image-20231022173657130

注意点:

1、PM开局为0

2、next数组下表为0的时候，开局就是-1

3、PM下标从1开始