題目鏈接
題目大意就是給你兩個字符串，求出第一個字符串在第二個字符串中出現的次數。

如果我們暴力匹配的話，復雜度是 len(first) * len(second) 對于題目給的
1e4 * 1e6 顯然暴力不可取， 這里就用到 KMP 。

說到 KMP 最難理解的就是 next 數組了下面給出了 next 數組的詳細求法。

我們先預設兩個指針，一個指向 i = 0 ，一個指向 j = -1 .應為兩個值如果設置成一樣，那么對應的字母一定也是一樣的，就完成不了我們想要的任務了。

從第一項開始我們默認他是匹配的，應為next數組的第一項就是 -1(當然這里數組下標是從0開始的)。默認他是匹配的（實際上這是一個邊界條件）我們進行next[++i] = ++j;
接下來我們i + 1 = 1， j + 1 = 0，我們有其對應的字母不一樣，我們進行
j = next[j]，知道又是匹配的我們進行next[++i] = ++j,
以此重復得到整個next數組。

實際上nex數組的表示意義就是這個點的前面的字符串能夠匹配的數組的最后一個下標

#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int N1 = 1e4 + 10, N2 = 1e6 + 10; char fir[N1], sec[N2]; int nex[N1]; void getnex() {int i = 0, j = -1, n = strlen(fir);while(i < n) {if(j == -1 || fir[i] == fir[j]) nex[++i] == ++j;else j = nex[j];} } int kmp() {int ans = 0;int i = 0, j = -1, lf = strlen(fir), ls = strlen(sec);while(i < ls) {if(j == -1 || fir[j] == sec[i]) i++, j++;else j = nex[j];if(j == lf) ans++, j = -1;}return ans; } int main() {int t;scanf("%d", &t);while(t--) {scanf("%s %s", fir, sec);nex[0] = -1;getnex();printf("%d\n", kmp());}return 0; }

總結

以上是生活随笔為你收集整理的hdu1686：KMP板子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。