KMP算法是主要用來做字符串的匹配，有一個文本次T和一個模式串P，就是拿模式串P去匹配文本串T。 匹配的步驟分為兩步，先做模式串自身匹配，即求出next數(shù)組；然后在進行T與P的匹配。 那么可能會問，為什么要做模式串自身匹配，這么做的優(yōu)點體現(xiàn)在哪里？next數(shù)組到底是干啥的？它的含義是什么？   怎么求next數(shù)組？ T與P的匹配過程具體是怎么操作的？

KMP算法，具體誰發(fā)明的就不說了，它主要的用途就是查找字符串，查找字符串"ab"(目標(biāo)字符串)在字符串"abc"(待查找字符串)中出現(xiàn)的位置。換句話說，就是查找字符串"abc"是否包含字符串"ab"，如果包含，返回包含的起始位置

如下兩個字符串：

str = "dabxabxababxabwabxad" (待查找字符串)

ptr = "abxabwabxad" (目標(biāo)字符串)

需要計算str中是否含有ptr，如果有，返回str中出現(xiàn)的起始位置，如果沒有，返回-1

通過肉眼觀察我們發(fā)現(xiàn)，str中是包含ptr的