hdu1686：KMP板子

题目链接
题目大意就是给你两个字符串，求出第一个字符串在第二个字符串中出现的次数。

如果我们暴力匹配的话，复杂度是 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;
}