結果

問題 No.2626 Similar But Different Name
ユーザー Nzt3Nzt3
提出日時 2024-02-12 12:27:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 191 ms / 3,000 ms
コード長 2,136 bytes
コンパイル時間 3,373 ms
コンパイル使用メモリ 249,164 KB
実行使用メモリ 44,728 KB
最終ジャッジ日時 2024-09-28 17:56:27
合計ジャッジ時間 7,672 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 1 ms
6,824 KB
testcase_05 AC 1 ms
6,816 KB
testcase_06 AC 1 ms
6,820 KB
testcase_07 AC 1 ms
6,820 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 2 ms
6,820 KB
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 2 ms
6,820 KB
testcase_12 AC 3 ms
6,816 KB
testcase_13 AC 3 ms
6,816 KB
testcase_14 AC 3 ms
6,820 KB
testcase_15 AC 3 ms
6,816 KB
testcase_16 AC 2 ms
6,820 KB
testcase_17 AC 3 ms
6,824 KB
testcase_18 AC 183 ms
44,596 KB
testcase_19 AC 47 ms
21,832 KB
testcase_20 AC 43 ms
21,828 KB
testcase_21 AC 41 ms
21,832 KB
testcase_22 AC 174 ms
35,924 KB
testcase_23 AC 175 ms
36,044 KB
testcase_24 AC 172 ms
34,080 KB
testcase_25 AC 174 ms
34,808 KB
testcase_26 AC 176 ms
36,028 KB
testcase_27 AC 181 ms
36,876 KB
testcase_28 AC 182 ms
36,360 KB
testcase_29 AC 179 ms
34,044 KB
testcase_30 AC 175 ms
34,916 KB
testcase_31 AC 175 ms
35,676 KB
testcase_32 AC 176 ms
36,944 KB
testcase_33 AC 176 ms
36,904 KB
testcase_34 AC 172 ms
34,084 KB
testcase_35 AC 173 ms
35,692 KB
testcase_36 AC 174 ms
34,216 KB
testcase_37 AC 191 ms
44,728 KB
権限があれば一括ダウンロードができます

ソースコード

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