結果
問題 | No.2626 Similar But Different Name |
ユーザー | Nzt3 |
提出日時 | 2024-02-12 12:27:37 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 225 ms / 3,000 ms |
コード長 | 2,136 bytes |
コンパイル時間 | 3,854 ms |
コンパイル使用メモリ | 249,888 KB |
実行使用メモリ | 44,592 KB |
最終ジャッジ日時 | 2024-02-12 12:27:50 |
合計ジャッジ時間 | 9,128 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 1 ms
6,676 KB |
testcase_04 | AC | 2 ms
6,676 KB |
testcase_05 | AC | 2 ms
6,676 KB |
testcase_06 | AC | 2 ms
6,676 KB |
testcase_07 | AC | 2 ms
6,676 KB |
testcase_08 | AC | 2 ms
6,676 KB |
testcase_09 | AC | 4 ms
6,676 KB |
testcase_10 | AC | 3 ms
6,676 KB |
testcase_11 | AC | 3 ms
6,676 KB |
testcase_12 | AC | 3 ms
6,676 KB |
testcase_13 | AC | 3 ms
6,676 KB |
testcase_14 | AC | 3 ms
6,676 KB |
testcase_15 | AC | 3 ms
6,676 KB |
testcase_16 | AC | 3 ms
6,676 KB |
testcase_17 | AC | 3 ms
6,676 KB |
testcase_18 | AC | 210 ms
44,592 KB |
testcase_19 | AC | 53 ms
21,952 KB |
testcase_20 | AC | 50 ms
21,952 KB |
testcase_21 | AC | 48 ms
21,952 KB |
testcase_22 | AC | 200 ms
36,020 KB |
testcase_23 | AC | 206 ms
36,168 KB |
testcase_24 | AC | 196 ms
34,204 KB |
testcase_25 | AC | 197 ms
35,028 KB |
testcase_26 | AC | 200 ms
36,148 KB |
testcase_27 | AC | 224 ms
36,912 KB |
testcase_28 | AC | 198 ms
36,352 KB |
testcase_29 | AC | 197 ms
34,192 KB |
testcase_30 | AC | 197 ms
35,024 KB |
testcase_31 | AC | 199 ms
35,800 KB |
testcase_32 | AC | 198 ms
36,948 KB |
testcase_33 | AC | 225 ms
36,912 KB |
testcase_34 | AC | 200 ms
34,212 KB |
testcase_35 | AC | 198 ms
35,820 KB |
testcase_36 | AC | 196 ms
34,212 KB |
testcase_37 | AC | 209 ms
44,592 KB |
ソースコード
#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'; }