POJ 3461

非常直白的KMP

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxw= 1e5+5;
const int maxt= 1e6+5;

char w[maxw], t[maxt];
int nxt[maxw];
int ans;

void PreKmp(int m)
{
    int i= 0, j;
    j= nxt[0]= -1;

    while (i< m){
        while (j> -1 && w[i]!= w[j]){
            j= nxt[j];
        }
        ++i;
        ++j;
        if (w[i]== w[j]){
            nxt[i]= nxt[j];
        }
        else{
            nxt[i]= j;
        }
    }
}
void Kmp(int p, int s)
{
    int i= 0, j= 0;
    while (j< s){
        while (i> -1 && w[i]!= t[j]){
            i= nxt[i];
        }

        ++i;
        ++j;
        if (i>=  p){
            ++ans;
            i= nxt[i];
        }
    }
}
int main()
{
    int kase;
    scanf("%d", &kase);
 
    while (EOF!= scanf(" %s", w) && EOF!= scanf(" %s", t)){
        int w_l= strlen(w), t_l= strlen(t);
        ans= 0;
        PreKmp(w_l);
        Kmp(w_l, t_l);
        cout<<ans<<endl;
    }

    return 0;
}

POJ 3461

原文：https://www.cnblogs.com/Idi0t-N3/p/12521920.html