結果
問題 | No.2626 Similar But Different Name |
ユーザー |
|
提出日時 | 2024-02-09 21:53:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 158 ms / 3,000 ms |
コード長 | 851 bytes |
コンパイル時間 | 2,669 ms |
コンパイル使用メモリ | 132,352 KB |
実行使用メモリ | 32,204 KB |
最終ジャッジ日時 | 2024-09-28 15:09:32 |
合計ジャッジ時間 | 6,425 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include<iostream>#include<cassert>#include<atcoder/string>#include<atcoder/modint>#include<atcoder/convolution>using namespace std;using mint=atcoder::modint998244353;int N,M,K;string S,T;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>N>>M>>K>>S>>T;vector<int>Z;{string a=T+S;for(char&c:a){if(c>='a')c='A'+(c-'a');}Z=atcoder::z_algorithm(a);}vector<mint>sU(N),sL(N),tU(M),tL(M);for(int i=0;i<N;i++){if(S[i]>='a')sL[i]=1;else sU[i]=1;}for(int i=0;i<M;i++){if(T[i]>='a')tL[i]=1;else tU[i]=1;}reverse(tU.begin(),tU.end());reverse(tL.begin(),tL.end());vector<mint>U=atcoder::convolution(sU,tU),L=atcoder::convolution(sL,tL);int ans=0;for(int i=0;i<=N-M;i++)if(Z[M+i]>=M){int c=U[M-1+i].val()+L[M-1+i].val();if(M-c>=1&&M-c<=K)ans++;}cout<<ans<<endl;}