| 18 | # 生成 next 数组 |
| 19 | # next[j] 表示下标 j 之前的模式串 p 中，最长相等前后缀的长度 |
| 20 | def generateNext(p: str): |
| 21 | m = len(p) |
| 22 | next = [0 for _ in range(m)] # 初始化数组元素全部为 0 |
| 23 | |
| 24 | left = 0 # left 表示前缀串开始所在的下标位置 |
| 25 | for right in range(1, m): # right 表示后缀串开始所在的下标位置 |
| 26 | while left > 0 and p[left] != p[right]: # 匹配不成功, left 进行回退, left == 0 时停止回退 |
| 27 | left = next[left - 1] # left 进行回退操作 |
| 28 | if p[left] == p[right]: # 匹配成功，找到相同的前后缀，先让 left += 1，此时 left 为前缀长度 |
| 29 | left += 1 |
| 30 | next[right] = left # 记录前缀长度，更新 next[right], 结束本次循环, right += 1 |
| 31 | |
| 32 | return next |
| 33 | |
| 34 | print(kmp("abbcfdddbddcaddebc", "ABCABCD")) |
| 35 | print(kmp("abbcfdddbddcaddebc", "bcf")) |