KMP算法

算法模板

//Author LJH
//www.cnblogs.com/tenlee
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define clc(a, b) memset(a, b, sizeof(a))
using namespace std;

const int inf = 0x3f;
const int INF = 0x3f3f3f3f;
const int maxn = 5e6+5;

char par[maxn], son[maxn];
int next[maxn];

void get_next()
{
    int len = strlen(son);
    next[0] = next[1] = 0; 
    for(int i = 1; i < len; i++)
    {
        int j = next[i];
        while(j && son[i] != son[j]) j = next[j];
        next[i+1] = son[i] == son[j] ? j+1 : 0;
    }
}
void kmp()
{
    get_next();

    int nu = 0;
    int nlen = strlen(par), mlen = strlen(son);
    int i = 0, j = 0;
    for(i = 0; par[i]; i++)
    {
        while(j && par[i] != son[j])
        {
            j = next[j];
        }
        if(par[i] == son[j]) 
        {
            j++;
        }
        if(j == mlen)
        {
            printf("case %d#  %d
", ++nu, i - mlen + 1);
            j = 0;
        }
    }
}

int main()
{
    while(true)
    {
        gets(son);
        gets(par);
        kmp();
    }
    return 0;
}