hihocoder 1015 KMP算法

传送门

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
const int N=1e6+10;
int f[N];
char a[N],b[N];
void getFail(int m)
{
    f[1]=0;
    int j=f[1];
    for(int i=2; i<=m; i++)
    {
        while(j>0&&b[i]!=b[j+1]) j=f[j];
        if(b[i]==b[j+1]) j++;
        f[i]=j;
    }
}
int find(int n,int m)
{
    int i,j=0,cnt=0;
    for(i=1; i<=n; i++)
    {
        while(j>0&&b[j+1]!=a[i]) j=f[j];
        if(b[j+1]==a[i]) j+=1;
        if(j==m)
        {
            cnt++;
        }
    }
    return cnt;
}
int main()
{
    int n=read();
    int m=2*n;
    for(int i=0;i<n;i++){
        scanf("%s %s",b+1,a+1);
        getFail(strlen(b+1));
        printf("%d
",find(strlen(a+1),strlen(b+1)));
    }
    return 0;
}

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
const int N=1e6+10;
int f[N];
char a[N],b[N];
void get_next(){
    int j=0,k=-1;
    f[0]=-1;
    int m=strlen(b);
    while(j<m){
        if(k==-1||b[j]==b[k]) f[++j]=++k;
        else k=f[k];
    }
}
int kmp_count(){
    int n=strlen(a),m=strlen(b);
    int i=0,j=0,res=0;
    while(i<n){
        if(j==-1||a[i]==b[j]) i++,j++;
        else j=f[j];
        if(j==m){
            res++;
            j=f[j];
        }
    }
    return res;
}
int main(){
    int T=read();
    while(T--) {
        scanf("%s%s",b,a);
        get_next();
        printf("%d
",kmp_count());
    }
    return 0;
}

#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
#define inf 1000000000000000LL
#define mod 1000000007
using namespace std;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
const int N=1e6+10;
char a[N],b[N];
int f[N];
void get_next(){
    int m=strlen(b);
    f[0]=f[1]=0;
    for(int i=1;i<m;i++){
        int j=f[i];
        while(j&&b[i]!=b[j]) j=f[j];
        f[i+1]=b[i]==b[j]?j+1:0;
    }
}
int kmp_count(){
    int n=strlen(a),m=strlen(b);
    int j=0,res=0;
    for(int i=0;i<n;i++){
        while(j&&b[j]!=a[i]) j=f[j];
        if(b[j]==a[i]) j++;
        if(j==m){
            res++;
            j=f[j];
            if(j>m) j=0;
        }
    }
    return res;
}
int main(){
    int n=read();
    while(n--) {
        scanf("%s%s",b,a);
        get_next();
        printf("%d
",kmp_count());
    }
    return 0;
}