KMP算法 笔记

先谈朴素的模式匹配算法

朴素顾名思义，简单，直白，但是带来的不便也是可想而知的，那么什么是朴素的模式匹配呢？最简单的来说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或者全部遍历完成为止。通俗来讲就是，从主串的第一个字符（a）起，依次与子串的每一位字符(dbce)进行匹配直到匹配成功或者全部遍历完成为止。当i=4时匹配成功。

那么如果字符数量非常大呢？时间复杂度当然也会非常大的，此时就应该应用KMP模式匹配算法。

如果T串中的字符没有重复，而T串的第二位与S串的第二位时相等的，那么在匹配的时候，T串的首位直接和S串的第三位开始匹配（这里只是假设第二位相同），这样就省略了朴素的模式匹配那样的第二步骤，同理，其他位相同也如此。这里会有这样的问题：假设，T串共六位字符，它的前五位与S串的前五位是相同的，那么T串要和S串的第六位判断，因为T[1]!=T[6],但是不能断定T[1]一定不等于S[6]，因此要进行这样的判断。

如果T串中的字符有重复，比如主串S=“aaaabcde”（下标为i）与字串T="aaaaax"（下标为j）

用KMP算法进行匹配的时候，会发现到第二，三，四，五步骤时是多余的，由于T串的第二，三，四，五，位置的字符都与首位“a”那么可以表示为i=6，j=1；