KMP

KMP

KMP算法要解决的问题就是在字符串（也叫主串）中的模式（pattern）定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字，如果它在一个主串中出现，就返回它的具体位置，否则返回-1（常用手段）。

Code of KMP count

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 1000100;

char m[maxn], n[maxn];
int nex[maxn];
///next[j]的值（也就是k）表示，当P[j] != T[i]时，j指针的下一步移动位置

void getne(char * str, int len)
{
    int i = 0, j = -1;
    nex[0] = -1;
    while(i < len)
    {
        if (j == -1 || str[i] == str[j])
            nex[++i] = ++j;
        else
            j = nex[j];
    }
}

int kmp(char * a, char * b, int lena, int lenb)
{
    int sum = 0;
    int i = 0, j = 0;
    while(i < lena && j < lenb)
    {
        ///当j为-1时,要移动的是i,当然j也要归0
        if (j == -1 || a[i] == b[j])
            ++j, ++i;
        else
            j = nex[j];
        if(j == lenb)
        {
            sum++;
            ///i--;会TLE
            j = nex[j];
        }
    }
    return sum;
}

int main()
{
    scanf("%s", n);///子串
    scanf("%s", m);///主串
    int a = strlen(n), b = strlen(m);
    getne(n, a);
    printf("%d\n", kmp(m, n, b, a));
}

参考1

参考2

参考3

参考4