kmp

next数组，对于模式串的某一位置 j ， next[j] 的值是该模式串从下标0到j-1的子串最大相等前缀和后缀数

s:       a b a a b c a b a
index:   0 1 2 3 4 5 6 7 8
next:	 -1 0 0 1 1 2 0 1 2

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int maxn = 1e5 + 10;
char a[maxn];//文本串
char b[maxn];//模式串
int kmp_next[maxn];

void get_next(int m)
{
    int j = 0;
    kmp_next[0] = 0;//初始化
    for (int i = 1; i <= m;++i)
    {
        //当这一位不匹配时，将j指向此为之前最大公共前后缀的位置
        while(j>0&&b[i]!=b[j])
            j = kmp_next[j-1];
        if (b[i] == b[j])//如果这一位匹配，那么将j+1，继续判断下一位
            ++j;
        kmp_next[i] = j;
    }
}

//找到b在a中第一次出现的位置
int find_pos(int n,int m)
{
    int i, j = 0;
    int p = -1;
    get_next(m);
    for (i = 0; i < n;++i)
    {
        while(j>0&&a[i]!=b[j]) j=kmp_next[j-1];
        if (a[i] == b[j]) ++j;
        if (j == m)
        {
            p = i - m + 1;
            break;
        }
    }
    //返回位置p的值
    return p;
}

//找到b在a中第k次出现的位置
int find_num(int n,int m,int k)
{
    int i, j = 0;
    int res = 0;
    get_next(m);
    for (i = 0; i < n;++i)
    {
        while(j>0&&a[i]!=b[j]) j=kmp_next[j-1];
        if (a[i] == b[j]) ++j;
        if (j == m)
            ++res;
    }
    //返回数量
    return res;
}