引言

這個KMP算法就是怎么說呢，就是不管算法競賽還是找工作筆試面試，都是非常愛問愛考的，其實也是因為這個算法比較難懂，其實就是很難，所以非常個人的一個思維邏輯吧，反正就是用來區(qū)分人的，我會你不會，那么我就比你牛逼，所以那就開始吧。

一、算法概念

這個KMP算法就是用來匹配字符串的，在一個字符串中是否有另一個字符串的存在，如果存在返回原始字符串中的初始下標

二、題目描述

給定一個字符串 S，以及一個模式串 P，所有字符串中只包含大小寫英文字母以及阿拉伯數(shù)字。模式串 P 在字符串 S 中多次作為子串出現(xiàn)。求出模式串 P 在字符串 S 中所有出現(xiàn)的位置的起始下標。輸入格式
第一行輸入整數(shù) N，表示字符串 P 的長度。
第二行輸入字符串 P。
第三行輸入整數(shù) M，表示字符串 S 的長度。
第四行輸入字符串 S。輸出格式
共一行，輸出所有出現(xiàn)位置的起始下標（下標從 0 開始計數(shù)），整數(shù)之間用空格隔開。數(shù)據(jù)范圍
1≤N≤105，1≤M≤106輸入樣例：
3
aba
5
ababa輸出樣例：
0 2

三、思路講解

這個KMP最重要的就是一個next數(shù)組，先來說一下這個是什么意思吧，next [i] 里面存的是在模板串中的以第i號下標為終點，和以第1號下標為起點的兩個字符串相等的話，它們的長度最長為 j ，也就是第 i 號位置的最大的后綴和前綴相等的最大長度是j

然后就是匹配算法了，如下圖如果說在模板串中，到第 j 號下標都匹配成功的話，原串的第 i 號下標和模板串的第 j+1號下標不匹配了，那么最暴力的做法就是將模板串往后移動一位，再重新一個一個匹配，那么KMP的想法是，我之前已經(jīng)匹配了那么些串了，那么能不能用一些性質(zhì)，來幫助我更加高效的匹配呢

然后又因為綠色的都是相等的，又因為我們有了next數(shù)組，可以知道當前的模板串往后移動的話，可以知道向后移動的最小距離是多少，又能夠使得從 [1, ne[j] ]的模板串跟從 [i - j + 1, i - 1]的字串是相等的， 也就是說能使每一次匹配的原串沒有浪費，都不用再重新匹配

三、代碼實現(xiàn)

然后這個KMP的話，下標一般是從1開始的

#include <iostream>using namespace std;const int N = 100010, M = 1000010;int n, m;
char p[N], s[M];
int ne[N];int main()
{cin >> n >> p + 1 >> m >> s + 1;//求next數(shù)組for(int i = 2, j = 0; i <= n; ++i)  //因為ne[1]就是0可以直接從2開始{while(j && p[i] != p[j+1]) j = ne[j];if(p[i] == p[j+1]) j++;ne[i] = j;}for(int i = 1, j = 0; i <= m; ++i){while(j && s[i] != p[j+1]) j = ne[j];if(s[i] == p[j+1]) j++;if(j == n){printf("%d ", i - n);j = ne[j];}}return 0;
}

四、測試