[个人笔记]算法笔记之KMP算法-字符串查找算法

对于长度为 n 的字符串 S,以及一个长度为 m (m<=n) 的字符串 s,寻找 s 在 S 中第一次出现的位置.

朴素的解法时间复杂度是 O(m×n)

KMP算法的时间复杂度是 O(m+n)

相比于朴素解法匹配失败就指针回退,KMP算法则是标记 S 的指针不回退,标记 s 的指针根据一个函数(回退函数,前缀函数,部分匹配表,失配函数等都是这个东西的翻译,似乎每个网站的翻译甚至同一个网站不同的作者翻译都是不一样的...)部分回退,从而节省了大量时间.

这个回退函数的基本原理就是通过预处理字符串 s ,找到 s 中前缀相同的部分,计算每个位置匹配失败的时候需要回退的值,以便于在匹配失败的时候不用整个后退.

所以关键问题就转化成了如何求解回退函数,基本思想就是寻找 s 中各个子串的最长公共前缀.

就写这么多吧,希望以后的自己能看懂.