結果

問題 No.2626 Similar But Different Name
ユーザー Nzt3Nzt3
提出日時 2024-02-12 12:22:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,128 bytes
コンパイル時間 3,726 ms
コンパイル使用メモリ 250,432 KB
実行使用メモリ 44,728 KB
最終ジャッジ日時 2024-09-28 17:56:19
合計ジャッジ時間 8,165 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 WA -
testcase_04 AC 2 ms
6,816 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 2 ms
6,820 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 3 ms
6,816 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
権限があれば一括ダウンロードができます

ソースコード

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]>='a')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]+c2[i]<=K&&c1[i]+c2[i]>=1)ans+=1;
    }
  }
  cout<<ans<<'\n';
}
0