結果
問題 | No.2626 Similar But Different Name |
ユーザー |
![]() |
提出日時 | 2024-02-09 23:38:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,198 bytes |
コンパイル時間 | 4,309 ms |
コンパイル使用メモリ | 255,268 KB |
最終ジャッジ日時 | 2025-02-19 04:16:38 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 6 WA * 9 TLE * 1 -- * 19 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define rep(i, n) for(int i=0;i<(n);++i) #define rep1(i, n) for(int i=1;i<=(n);i++) #define ll long long using mint = modint998244353; using P = pair<ll,ll>; using lb = long double; using T = tuple<ll, ll, ll>; #ifdef LOCAL # include <debug_print.hpp> # define dbg(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define dbg(...) (static_cast<void>(0)) #endif template< unsigned mod > struct RollingHash { vector< unsigned > hashed, power; inline unsigned mul(unsigned a, unsigned b) const { unsigned long long x = (unsigned long long) a * b; unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m; asm("divl %4; \n\t" : "=a" (d), "=d" (m) : "d" (xh), "a" (xl), "r" (mod)); return m; } //コンストラクタ(文字列) RollingHash(const string &s, unsigned base = 10007) { int sz = (int) s.size(); hashed.assign(sz + 1, 0); power.assign(sz + 1, 0); power[0] = 1; for(int i = 0; i < sz; i++) { power[i + 1] = mul(power[i], base); hashed[i + 1] = mul(hashed[i], base) + s[i]; if(hashed[i + 1] >= mod) hashed[i + 1] -= mod; } } //[l,r)のハッシュ値を得る unsigned get(int l, int r) const { unsigned ret = hashed[r] + mod - mul(hashed[l], power[r - l]); if(ret >= mod) ret -= mod; return ret; } //ハッシュをつなげる unsigned connect(unsigned h1, int h2, int h2len) const { unsigned ret = mul(h1, power[h2len]) + h2; if(ret >= mod) ret -= mod; return ret; } int LCP(const RollingHash< mod > &b, int l1, int r1, int l2, int r2) { int len = min(r1 - l1, r2 - l2); int low = -1, high = len + 1; while(high - low > 1) { int mid = (low + high) / 2; if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid; else high = mid; } return (low); } }; using RH = RollingHash< 1000000007 >; //segtreeに乗せる用 // long long mod = 2147483647; // struct S { // long long hash, pow; // }; // S op(S a, S b){ // long long na = a.hash * b.pow + b.hash; // na %= mod; // return {na, (a.pow * b.pow) % mod}; // } // S e(){ // return {0,1}; // } int main() { int n, m, k; cin >> n >> m >> k; string s, t; cin >> s >> t; reverse(t.begin(),t.end()); vector<vector<ll>> a(26, vector<ll>(n)), b(26, vector<ll>(m)); rep(i,n){ if(isupper(s[i])) a[s[i]-'A'][i] = 1; else a[s[i]-'a'][i] = -1; } rep(i,m){ if(isupper(t[i])) b[t[i]-'A'][i] = 1; else b[t[i]-'a'][i] = -1; } dbg(a,b); vector<vector<ll>> f(26); rep(i,26) f[i] = convolution_ll(a[i], b[i]); dbg(f[0]); reverse(t.begin(),t.end()); rep(i,n){ if(isupper(s[i])) s[i] = s[i]+32; } rep(i,m){ if(isupper(t[i])) t[i]=t[i]+32; } dbg(s, t); RH S(s), T(t); int ans = 0; rep(i,n){ if(T.get(0,m)!=S.get(i,i+m)) continue; int c = 0; rep(j,26){ if(f[j][i+m-1]<=0) c-=f[j][i+m-1]; } dbg(i,c); if(c<=k && c>=1) ans++; } cout << ans << endl; return 0; }