如果让你从一个长字符串中匹配另一个字符串，你会怎么去查？大多数人的第一反馈是从第一位开始匹配，如果匹配不胜利，接着从第二位开始从新匹配，以此类推，直至齐全匹配为止。然而匹配的字符有些局部前缀实际上是雷同的，那么从这点思考，有没有一些别的算法能够精简这步反复匹配操作呢。本文将介绍一种算法，KMP（Knuth-Morris-Pratt）。
要学习KMP算法，首先要了解字符串前缀后缀的含意，打个比方，"KnuthKn"，它的前缀有K,Kn,Knu,Knut,Knuth,KnuthK，后缀有n,Kh,hKn,thKn,uthKn,nuthKn。而后咱们定义一个局部匹配表，它会记录字符串每一位的前缀后缀雷同字符串的长度。比方字符串前五位是Knuth，它们的前后缀没有匹配字符串，所以在局部匹配表里第五位是0；又比方前七位是KnuthKn，它们前后缀匹配的字符串是Kn，字符串长度为2，所以局部匹配表里第五位就是2。由此可得，"KnuthKn"的局部匹配表为table=[0000012]。
那么，能够跳过后面字符串位数的公式为
partial_match_length - table[partial_match_length - 1]partial_match_length为已匹配字符长度，table为局部匹配表，下标从0开始。
如果这个工夫，拿"KnuthKn"去匹配一个任意长度的字符串"KnuKnuthKzKnuthKn",当匹配到第三位的时候，发现不匹配，这个工夫，执行上述公式，3-0=3，所以，跳过的长度为3，于是，下一次比对不须要从第三位开始，而是从第四位开始。当匹配到第十位的时候，又发现不匹配，则须要跳过6-1=5位，下一次从第9位开始。
然而在理论利用中，少数公司并没有采纳KMP这种算法，甚至JDK外部的String.contains办法也是应用的是暴力匹配的办法，因为优化足以反对失常的应用。
算法的思维越简略，理论利用的成果越好