結果

問題 No.2626 Similar But Different Name
コンテスト
ユーザー Nzt3
提出日時 2024-02-12 12:27:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 211 ms / 3,000 ms
コード長 2,136 bytes
コンパイル時間 3,903 ms
コンパイル使用メモリ 236,624 KB
最終ジャッジ日時 2025-02-19 05:36:16
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/convolution>
using namespace std;
using ll=long long;
using ull= unsigned long long;

namespace Lib{
  struct Rolling_hash{
    static constexpr ll rMOD=(1ll<<61)-1;
    ull base,inv;
    vector<ull> hash_val,pw;
    Rolling_hash(string St,unsigned b){
      vector<ull> S(St.begin(),St.end());
      base=b;
      ull c=1,t=base;
      ull h=0;
      pw.push_back(1);
      hash_val.push_back(0);
      for(int i=0;i<(int)S.size();i++){
        h=(mul(h,base)+S[i])%rMOD;
        hash_val.push_back(h);
        pw.push_back(mul(pw.back(),base));
      }
    }
    Rolling_hash(vector<ull> S,unsigned b){
      base=b;
      ull c=1,t=base;
      ull h=0;
      pw.push_back(1);
      hash_val.push_back(0);
      for(int i=0;i<(int)S.size();i++){
        h=(mul(h,base)+S[i])%rMOD;
        hash_val.push_back(h);
        pw.push_back(mul(pw.back(),base));
      }
    }
    constexpr ull mul(ull a,ull b){
      ull a1=a/(1ull<<31),a2=a%(1ull<<31),b1=b/(1ull<<31),b2=b%(1ull<<31);
      ull ret=0;
      ret=(ret+a1*b1*2)%rMOD;
      ull mid=a1*b2+b1*a2;
      ret=(ret+mid/(1ull<<30)+(mid%(1ull<<30))*(1ull<<31))%rMOD;
      ret=(ret+a2*b2)%rMOD;
      return ret;
    }
    ull get(int l,int r){
      assert(l<r);
      return (hash_val[r]-mul(hash_val[l],pw[r-l])+rMOD)%rMOD;
    }
  };
} // namespace Lib



int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N,M,K;
  cin>>N>>M>>K;
  string S,T;
  cin>>S>>T;
  constexpr int base=1400032941;
  string lowS=S,lowT=T;
  for(auto &i:lowS){
    if(i<='Z')i^=32;
  }
  for(auto &i:lowT){
    if(i<='Z')i^=32;
  }
  Lib::Rolling_hash hS(lowS,base),hT(lowT,base);
  vector Si(N,0),Ti(M,0);
  for(int i=0;i<N;i++){
    if(S[i]>='a')Si[i]=1;
  }
  for(int i=0;i<M;i++){
    if(T[i]<='Z')Ti[i]=1;
  }
  reverse(Ti.begin(),Ti.end());
  auto c1=atcoder::convolution(Si,Ti);
  for(auto &i:Si)i=1-i;
  for(auto &i:Ti)i=1-i;
  auto c2=atcoder::convolution(Si,Ti);
  int ans=0;
  for(int i=M;i<=(int)S.size();i++){
    if(hS.get(i-M,i)==hT.get(0,M)){
      if(c1[i-1]+c2[i-1]<=K&&c1[i-1]+c2[i-1]>=1)ans+=1;
    }
  }
  cout<<ans<<'\n';
}
0