ハッシュやるだけ。
理想的ハッシュを使ったらWAしたのでダメなハッシュを使った。
というよりも、どうやらこのコードにある'P'も結構ハッシュの衝突具合に影響を及ぼすらしくて、小さいとかぶるっぽい。仕組みがよく分からないので数学の人なんとかして
#include<stdio.h> #include<algorithm> #include<string.h> #include<vector> using namespace std; typedef unsigned long long wolf; char S[310000]; char T[310000]; long long pow[310000]; wolf P=1299709; //long long mod=1145148931919LL; int main(){ scanf("%s%s",S,T); int n=strlen(S); int m=strlen(T); pow[0]=1; for(int i=1;i<310000;i++)pow[i]=pow[i-1]*P; //for(int i=0;i<10;i++)printf("%lld\n",pow[i]); vector<wolf>v; wolf val=0; for(int i=0;i<m;i++)val=(val+(T[i])*pow[i]); for(int i=0;i<m;i++){ for(int j=0;j<26;j++){ if(T[i]-'a'==j)continue; wolf tmp=(val-(T[i])*pow[i]); v.push_back((tmp+pow[i]*('a'+j))); // printf("%d %d: %lld\n",i,j,(tmp+pow[i]*j)%mod); } for(int j=0;j<26;j++){ if(T[i]-'A'==j)continue; wolf tmp=(val-(T[i])*pow[i]); v.push_back((tmp+pow[i]*('A'+j))); // printf("%d %d: %lld\n",i,j,(tmp+pow[i]*j)%mod); } } std::sort(v.begin(),v.end()); int ret=0; wolf now=0; for(int i=n-1;i>=0;i--){ now=now*P; if(i<n-m)now=(now-(S[i+m])*pow[m]); now=(now+(S[i])); if(i<=n-m&&binary_search(v.begin(),v.end(),now))ret++; } printf("%d\n",ret); }