T4白兔的字符串悬赏一个解决方案

image

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=1e6+10,mod=1e9+7;
unordered_map<int,bool>m;
string a,t,b;
int h[M],p[M],h1,_,sum;
signed main(){
    cin>>a;
    t=" "+a+a;
    int n=t.size()-1;
    for(int i=1;i<=n;i++){
        h1=0;
        for(int j=i;j<=n+i-1;j++) h1=((h1*131+t[j])%mod+mod)%mod;
        p[i]=((p[i-1]*131)%mod+mod)%mod;
        m[h1]=1;
    }
    cin>>_;
    for(int i=1;i<=_;i++){
        cin>>b;
        b=" "+b;
        int m1=b.size()-1;
        for(int j=1;j<=m1;j++) h[i]=((h[i-1]*131+b[i])%mod+mod)%mod;
        for(int j=1;j<=m1-n+1;j++){
            int l=j,r=j+n-1;
            int h2=((h[r]-h[l-1]*p[n])%mod+mod)%mod;
            if(m[h2]) sum++;
        }
        cout<<sum<<endl;
    }
}

WA0

1 个赞

@HIM @李予劼

1 个赞