本文主要是介绍字符串匹配的KMP算法（The Knuth-Morris-Pratt Algorithm），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前言
字符串匹配是计算机的基本任务之一。
KMP算法的思想
1. 首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。
2. 因为B与A不匹配，搜索词再往后移。
3. 就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。
4.接着比较字符串和搜索词的下一个字符，还是相同。
5.直到字符串有一个字符，与搜索词对应的字符不相同为止。
6.这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。
7.一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。
做法：可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。
8.
这篇关于字符串匹配的KMP算法（The Knuth-Morris-Pratt Algorithm）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
