KMP模板

这里介绍几个说的比较好的博客：

接下的就是模板：

求模式串第一次在主串出现的位置 or 匹配是否在主串出现过 :

#include<bits/stdc++.h>
const int maxn = 1e6 + 10;
char mo[maxn], str[maxn];///mo为模式串、str为主串
int next[maxn];
inline void GetNext()
{
    int i = 0, j = -1, len = strlen(mo);
    next[i] = j;
    while(i < len){
        while( j != -1 && mo[i] != mo[j]) j = next[j];
        next[++i] = ++j;
    }
}
int KmpIndex()
{
    GetNext();
    int i =0, j = 0, strL = strlen(str), moL = strlen(mo);
    while(i < strL && j < moL){
        while( j != -1 && str[i] != mo[j]) j = next[j];
        i++, j++;
    }
    if(j == moL) return i - moL;///返回模式串在主串中首次出现的位置
    else return -1;
}
int main(void)
{
    scanf("%s %s", str, mo);
    printf("%d
", KmpIndex());
    return 0;
}

View Code

求出现次数：

#include<bits/stdc++.h>
const int maxn = 1e6 + 10;
char mo[maxn], str[maxn];///mo为模式串、str为主串
int next[maxn];
inline void GetNext()
{
    int i = 0, j = -1, len = strlen(mo);
    next[i] = j;
    while(i < len){
//        if(j == -1 || mo[i] == mo[j]) next[++i] = ++j;
//        else j = next[j];
        while( j != -1 && mo[i] != mo[j]) j = next[j];
        next[++i] = ++j;
    }
}
int KmpCount()///计算模式串在子串出现的次数
{
    GetNext();
    int i = 0, j = 0, strL = strlen(str), moL = strlen(mo);
    int ans = 0;
    while(i < strL){
        while( j != -1 && mo[j] != str[i]) j = next[j];
        i++, j++;
        if(j == moL) ans++;
    }
    return ans;///返回模式串在主串中出现的次数(可重叠出现)
}
int main(void)
{
    scanf("%s %s", str, mo);
    printf("%d
", KmpCount());
    return 0;
}

View Code

拓展KMP的模板：

#include <iostream>
#include <string>

using namespace std;

/* 求解 T 中 next[]，注释参考 GetExtend() */
void GetNext(string & T, int & m, int next[])
{
    int a = 0, p = 0;
    next[0] = m;

    for (int i = 1; i < m; i++)
    {
        if (i >= p || i + next[i - a] >= p)
        {
            if (i >= p)
                p = i;

            while (p < m && T[p] == T[p - i])
                p++;

            next[i] = p - i;
            a = i;
        }
        else
            next[i] = next[i - a];
    }
}

/* 求解 extend[] */
void GetExtend(string & S, int & n, string & T, int & m, int extend[], int next[])
{
    int a = 0, p = 0;
    GetNext(T, m, next);

    for (int i = 0; i < n; i++)
    {
        if (i >= p || i + next[i - a] >= p) // i >= p 的作用：举个典型例子，S 和 T 无一字符相同
        {
            if (i >= p)
                p = i;

            while (p < n && p - i < m && S[p] == T[p - i])
                p++;

            extend[i] = p - i;
            a = i;
        }
        else
            extend[i] = next[i - a];
    }
}

int main()
{
    int next[100];
    int extend[100];
    string S, T;
    int n, m;
    
    while (cin >> S >> T)
    {
        n = S.size();
        m = T.size();
        GetExtend(S, n, T, m, extend, next);

        // 打印 next
        cout << "next:   ";
        for (int i = 0; i < m; i++)
            cout << next[i] << " ";
 
        // 打印 extend
        cout << "
extend: ";
        for (int i = 0; i < n; i++)
            cout << extend[i] << " ";

        cout << endl << endl;
    }
    return 0;
}

View Code