結果

問題 No.2626 Similar But Different Name
コンテスト
ユーザー KKT89
提出日時 2024-02-09 22:46:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 199 ms / 3,000 ms
コード長 5,339 bytes
コンパイル時間 2,852 ms
コンパイル使用メモリ 229,640 KB
最終ジャッジ日時 2025-02-19 03:59:10
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

// https://github.com/kth-competitive-programming/kactl/blob/main/content/numerical/FastFourierTransform.h
// https://github.com/kth-competitive-programming/kactl/blob/main/content/numerical/FastFourierTransformMod.h
#include<complex>
struct FFT{
    using cpx = complex<double>;

    void fft(vector<cpx>& a){
        int n = a.size(), L = 0;
        while(n > 1){
            n >>= 1;
            L++;
        }
        n = a.size();
        static vector<complex<long double>> R(2, 1);
        static vector<cpx> rt(2, 1);  // (^ 10% faster if double)
        for(static int k = 2; k < n; k *= 2) {
            R.resize(n);
            rt.resize(n);
            auto x = polar(1.0L, acos(-1.0L) / k);
            for(int i = k; i < 2 * k; ++i) {
                rt[i] = R[i] = i & 1 ? R[i / 2] * x : R[i / 2];
            }
        }
        vector<int> rev(n);
        for(int i = 0; i < n; ++i) {
            rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
        }
        for(int i = 0; i < n; ++i) {
            if(i < rev[i]) swap(a[i], a[rev[i]]);
        }
        for(int k = 1; k < n; k *= 2){
            for(int i = 0; i < n; i += 2 * k) {
                for(int j = 0; j < k; ++j) {
                    cpx z = rt[j + k] * a[i + j + k];
                    a[i + j + k] = a[i + j] - z;
                    a[i + j] += z;
                }
            }
        }
    }

    vector<ll> conv(const vector<ll>& a, const vector<ll>& b){
        if(a.empty() or b.empty()) return {};
        vector<ll> res(a.size() + b.size() - 1);
        int L = 0, n = 1;
        while(n <= res.size()) {
            n <<= 1;
            L++;
        }

        vector<cpx> in(n), out(n);
        copy(a.begin(), a.end(), begin(in));
        for(int i = 0; i < b.size(); ++i) {
            in[i].imag(b[i]);
        }
        fft(in);
        for(cpx& x : in) x *= x;
        for(int i = 0; i < n; ++i) {
            out[i] = in[-i & (n - 1)] - conj(in[i]);
        }
        fft(out);
        for(int i = 0; i < res.size(); ++i) {
            res[i] = llround(imag(out[i]) / (4 * n));
        }
        return res;
    }

    vector<ll> convmod(const vector<ll>& a, const vector<ll>& b, int mod){
        if(a.empty() or b.empty()) return {};
        vector<ll> res(a.size() + b.size() - 1);
        int B = 0, n = 1, cut = (int)sqrt(mod);
        while(n <= res.size()) {
            n <<= 1;
            B++;
        }
        vector<cpx> L(n), R(n), outs(n), outl(n);
        for(int i = 0; i < a.size(); ++i) {
            L[i] = cpx((int)a[i] / cut, (int)a[i] % cut);
        }
        for(int i = 0; i < b.size(); ++i) {
            R[i] = cpx((int)b[i] / cut, (int)b[i] % cut);
        }
        fft(L);
        fft(R);
        for(int i = 0; i < n; ++i) {
            int j = -i & (n - 1);
            outl[j] = (L[i] + conj(L[j])) * R[i] / (2.0 * n);
            outs[j] = (L[i] - conj(L[j])) * R[i] / (2.0 * n) / 1i;
        }
        fft(outl);
        fft(outs);
        for(int i = 0; i < res.size(); ++i) {
            ll av = ll(real(outl[i]) + .5), cv = ll(imag(outs[i]) + .5);
            ll bv = ll(imag(outl[i]) + .5) + ll(real(outs[i]) + .5);
            res[i] = ((av % mod * cut + bv) % mod * cut + cv) % mod;
        }
        return res;
    }
};

vector<int> Zalgo(string s){
    int n=s.size();
    vector<int> a(n,0);
    int from=-1,last=-1;
    for(int i=1;i<n;i++){
        int &same=a[i];
        if(from!=-1){
            same=min(a[i-from],last-i);
            same=max(0,same);
        }
        while(i+same<n&&s[same]==s[i+same]){
            same++;
        }
        if(last<i+same){
            last=i+same;
            from=i;
        }
    }
    a[0]=n;
    return a;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m,k; cin >> n >> m >> k;
    string s,t; cin >> s >> t;

    vector<bool> ok(n);
    {
        string S = s, T = t;
        for (int i = 0; i < n; ++i) {
            if (s[i] >= 'a') {
                S[i] -= 'a';
                S[i] += 'A';
            }
        }
        for (int i = 0; i < m; ++i) {
            if (t[i] >= 'a') {
                T[i] -= 'a';
                T[i] += 'A';
            }
        }
        T = T + "$" + S;
        auto Z = Zalgo(T);
        for (int i = 0; i < n; ++i) {
            if (Z[m+1+i] >= m) {
                ok[i] = true;
            }
        }
    }
    vector<ll> sb(n), tb(m);
    for (int i = 0; i < n; ++i) {
        if (s[i] >= 'a') sb[i] = 1;
        else sb[i] = -1;
    }
    for (int i = 0; i < m; ++i) {
        if (t[i] >= 'a') tb[m-1-i] = 1;
        else tb[m-1-i] = -1;
    }
    FFT fft;
    auto conv = fft.conv(sb, tb);
    int res = 0;
    for (int i = 0; i < n; ++i) {
        if (ok[i]) {
            int idx = i+m-1;
            if (m-k-k <= conv[idx] and conv[idx] < m) {
                res += 1;
            }
        }
    }
    cout << res << endl;
}
0