文/Beta-TNT
作为一种经典的字符串/序列匹配算法，我相信所有系统学过计算机课程或者计算机语言的同学都接触过KMP匹配算法。关于KMP算法本身在这里就不再赘述，想要温习的朋友在网上随便一搜就有。这里想讨论的是针对KMP算法的一项实用化改进：在所有KMP算法的教学中，使用的都是定长目标字符串。虽然便于讲解，也覆盖了绝大多数应用场景，但算法本身仍然还有一个没被挖掘的潜力：搜索起始指针j不必回溯。因此实际上KMP算法可以用于匹配一个不固定长度，或者长度无限的目标串。在网络安全领域中经常有这种需求，需要持续检查某个时序数据序列片段是否满足某种特征，这个时序数据序列的长度一般认为是无限长/无法预估长度的，在这里使用KMP算法就非常合适。
具体实现比较简单。算法当然不必缓存一个无限长的目标串序列，只需要缓存当前和模式串长度相同的片段即可。在实现中可以使用一个最大长度和模式串长度相等的定长队列作为这个缓存，并按直觉习惯，约定使用方式为队尾进（append）队首出（pop left）。当队列满的时候append，会自动pop left队首元素。由此就构造了一个持续向右的单向滑动窗。
| Window | ||||||||||
| Target | … | a | b | a | b | a | b | a | b | … |
| Pattern | a | b | a | b | b | |||||
如果不想费脑子实现KMP算法，每次队列写满的时候判断队列内容和模式串是否匹配即可，如果失配就将窗口向右滑动一个字符（队尾插入下一个字符，队首字符自动出队），这就是最简单的暴力匹配算法在不定长度序列上的应用。换成KMP算法的话，失配时向右滑动的距离（队首出队元素的数量）等于失配时搜索模式串的指针i减去next[i]，并且将下一次搜索起始位指针j设置为next[i]，仅当窗口写满时才开始匹配。举例如下：
| Index | 0 | 1 | 2 | 3 | 4 |
| Pattern | a | b | a | b | b |
| Next | 0 | 0 | 0 | 1 | 2 |
| Window | ||||||||||||||
| Target | a | b | a | b | a | b | a | b | b | |||||
| Pattern | a | b | a | b | b | |||||||||
| Next | 0 | 0 | 0 | 1 | 2 | |||||||||
| Index | 0 | 1 | 2 | 3 | 4 | |||||||||
| Window | ||||||||||||
| Target | a | b | a | b | a | b | a | b | b | |||
| Pattern | a | b | a | b | b | |||||||
| Next | 0 | 0 | 0 | 1 | 2 | |||||||
| Index | 0 | 1 | 2 | 3 | 4 | |||||||
| Window | |||||||||
| Target | a | b | a | b | a | b | a | b | b |
| Pattern | a | b | a | b | b | ||||
| Next | 0 | 0 | 0 | 1 | 2 | ||||
| Index | 0 | 1 | 2 | 3 | 4 | ||||
| Window | |||||||||
| Target | a | b | a | b | a | b | a | b | b |
| Pattern | a | b | a | b | b | ||||
| Next | 0 | 0 | 0 | 1 | 2 | ||||
| Index | 0 | 1 | 2 | 3 | 4 | ||||
| Window | |||||||||
| Target | a | b | a | b | a | b | a | b | b |
| Pattern | a | b | a | b | b | ||||
| Next | 0 | 0 | 0 | 1 | 2 | ||||
| Index | 0 | 1 | 2 | 3 | 4 | ||||
| Window | |||||||||
| Target | a | b | a | b | a | b | a | b | b |
| Pattern | a | b | a | b | b | ||||
| Next | 0 | 0 | 0 | 1 | 2 | ||||
| Index | 0 | 1 | 2 | 3 | 4 | ||||
| Window | |||||||||
| Target | a | b | a | b | a | b | a | b | b |
| Pattern | a | b | a | b | b | ||||
| Next | 0 | 0 | 0 | 1 | 2 | ||||
| Index | 0 | 1 | 2 | 3 | 4 | ||||
| Window | |||||||||
| Target | a | b | a | b | a | b | a | b | b |
| Pattern | a | b | a | b | b | ||||
| Next | 0 | 0 | 0 | 1 | 2 | ||||
| Index | 0 | 1 | 2 | 3 | 4 | ||||
其实以上过程就是经典的KMP算法教学讲解过程，只不过我使用了“滑动窗”替代了经典教案里的“滑动模式串”，本质没有区别。为了实现匹配无限长序列，我使用数据追加（feed data）机制，将单个字符（或者其他待匹配数据）依次插入窗口队列尾。如果窗口内容满足匹配模式，则返回匹配子串在不定长序列中的起始下标（第一个插入队列的数据下标记为0，后续数据依次加1），以及匹配到的内容；否则返回空值。
我已经实现了Python版本代码，详见我的github：https://github.com/Beta-TNT/KMP_Unlimited/blob/main/kmp_unlimited.py