1.KMP

看 猫 片

#include<iostream>
using namespace std;
const int maxn=1e4+7;
int kmp[maxn];
void kmp_pre(char x[],int m){
    int i,j;
    j=kmp[0]=-1;
    i=0;
    while(i<m){
        while(j!=-1&&x[i]!=x[j]) j=kmp[j];
        kmp[++i]=++j;
    }
}
int kmp_count(char x[],int m,char y[],int n){
    int i,j;
    kmp_pre(x,m);
    i=j=0;
    while(i<n){
        while(j!=-1&&y[i]!=x[j]) j=kmp[j];
        i++;j++;
        if(j>=m){
            return i-j+1;
        }
    }
}