【不一样的题解】KMP算法和字符串哈希

1、KMP算法和next数组

#include<bits/stdc++.h>
using namespace std;
#define int long long
string s,t="ac";
int n,m,nxt[1110];
void init(){
    n=s.size();
    m=t.size();
    s=' '+s;
    t=' '+t;
}
void make(){
    nxt[1]=0;
    int j=nxt[1];
    for(int i=2;i<=m;i++){
        while(j!=0&&t[j+1]!=t[i])j=nxt[j];
        if(t[j+1]==t[i])j++;
        nxt[i]=j;
    }
}
int match(){
    int j=0,res=0;
    for(int i=1;i<=n;i++){
        while(j!=0&&s[i]!=t[j+1])j=nxt[j];
        if(s[i]==t[j+1])j++;
        if(j==m){
            res++;
        }
    }
    return res;
}
signed main(){
    cin>>s;
    init();
    make();
    cout<<match();
    return 0;
}

2、字符串哈希

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Hash{
    int base,mod,h[1110],pw[1110];
    void init(int Base,int Mod){
        base=Base,mod=Mod;
        pw[0]=1;
        for(int i=1;i<1110;i++)pw[i]=pw[i-1]*base%mod;
    }
    void make(string s){
        h[0]=s[0]%mod;
        for(int i=1;i<s.size();i++){
            h[i]=(h[i-1]*base%mod+s[i])%mod;
        }
    }
    int get(int L,int R){
        return (h[R]-h[L-1]*pw[R-L+1]%mod+mod)%mod;
    }
}ac,tmp;
string s,t="ac";
signed main(){
    cin>>s;
    ac.init(128,998244353);
    tmp.init(128,998244353);
    ac.make(s);
    tmp.make(t);
    int cnt=0,value=tmp.get(0,t.size()-1);
    for(int i=1;i<s.size();i++){
        if(ac.get(i-1,i)==value)cnt++;
    }
    cout<<cnt;
    return 0;
}