HPU Summer Training Day 32（河南理工大学暑期第三十二天）

把今天的这两个板子贴一下，完事了。

kmp

#include<bits/stdc++.h>

using namespace std;
string s,t;
int n,m;
vector<int> cal_nxt(string s){
    int n=(int)s.length();
    vector<int> nxt(n);
    for(int i=1;i<n;i++){
        int j=nxt[i-1];
        while(s[i]!=s[j]&&j>0) j=nxt[j-1];
        if(s[i]==s[j]) j++;
        nxt[i]=j;
    }
    return nxt;
}
int main(){
    cin>>s>>t;
    m=t.length();
    n=s.length();
    string T=t+'#'+s;
    vector<int> nxt=cal_nxt(T);
    for(int i=m+1;i<(int)T.length();i++){
        if(nxt[i]==m){
            cout<<"YES"<<endl;return 0;
        }
    }
    cout<<"NO"<<endl;
    return 0;
}

hash

#include<bits/stdc++.h>

using namespace  std;
typedef unsigned long long ull;
const ull base = 2333;
const ull mod = 1e9+9;
const int N = 1e6+100;
ull hashes[N],p[N];
ull gethashes(int l,int r){
    return (hashes[r]%mod-(hashes[l-1]%mod*p[r-l+1]%mod)%mod+mod)%mod;
}
char s[N],t[N];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s %s",t+1,s+1);
        int n=strlen(s+1);
        int m=strlen(t+1);
        p[0]=1;
        for(int i=1;i<=n;i++){
            hashes[i]=(hashes[i-1]*base%mod+s[i]%mod)%mod;
            p[i]=(p[i-1]%mod*base%mod)%mod;
        }
        ull ans=0;
        for(int i=1;i<=m;i++) ans=(ans*base%mod+t[i]%mod)%mod;
        int res=0;
        for(int i=m;i<=n;i++){
            if(gethashes(i-m+1,i)==ans){
                res++;
            }
        }
        printf("%d\n",res);
    }
    return 0;
}