kmp算法的原理和步驟

1）、KMP是一個解決模式串在文本串是否出現過，如果出現過，最早出現的位置的經典算法

2）、Knuth-Morris-Pratt 字符串查找算法，簡稱為 “KMP算法”，常用於在一個文本串S內查找一個模式串P 的出現位置，這個算法由Donald Knuth、Vaughan Pratt、James H. Morris三人於1977年聯合發表，故取這3人的姓氏命名此算法.

3）、KMP方法算法就利用之前判斷過信息，通過一個next數組，保存模式串中前後最長公共子序列的長度，每次回溯時，通過next數組找到，前面匹配過的位置，省去了大量的計算時間。

KMP算法是根據三位作者（h，is和t）的名字來命名的，算法的全稱是Knuth Morris Pratt算法，簡稱為KMP算法。

KMP算法的核心思想，跟上一節講的BM算法非常相近。我們假設主串是a，模式串是b。在模式串與主串匹配的過程中，當遇到不可匹配的字符的時候，我們希望 找到一些規律，可以將模式串往後多滑動幾位，跳過那些肯定不會匹配的情況。

在模式串和主串匹配的過程中，把不能匹配的那個字符仍然叫作壞字符，把已經匹配的 那段字符串叫作好前綴。