如果让你从一个长字符串中匹配另一个字符串，你会怎么去查？大多数人的第一反馈是从第一位开始匹配，如果匹配不胜利，接着从第二位开始从新匹配，以此类推，直至齐全匹配为止。然而匹配的字符有些局部前缀实际上是雷同的，那么从这点思考，有没有一些别的算法能够精简这步反复匹配操作呢。本文将介绍一种算法，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 办法也是应用的是暴力匹配的办法，因为优化足以反对失常的应用。
算法的思维越简略，理论利用的成果越好